@article{19859, abstract = {We consider a recently introduced model of color-avoiding percolation (abbreviated CA-percolation) defined as follows. Every edge in a graph G is colored in some of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k-1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components. We study the component structure of a randomly colored Erdős–Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors.}, author = {Lichev, Lyuben and Schapira, Bruno}, issn = {2644-9463}, journal = {Annales Henri Lebesgue}, pages = {35--65}, publisher = {École normale supérieure de Rennes}, title = {{Color-avoiding percolation on the Erdős–Rényi random graph}}, doi = {10.5802/ahl.228}, volume = {8}, year = {2025}, } @article{19879, abstract = {We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors.}, author = {Dvořák, Zdeněk and Moore, Benjamin and Seifrtová, Michaela and Šámal, Robert}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Precoloring extension in planar near-Eulerian-triangulations}}, doi = {10.1016/j.ejc.2025.104138}, volume = {127}, year = {2025}, } @inproceedings{20007, abstract = {There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.}, author = {Anastos, Michael and Kwan, Matthew Alan and Moore, Benjamin}, booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing}, isbn = {9798400715105}, issn = {0737-8017}, location = {Prague, Czechia}, pages = {2098--2106}, publisher = {Association for Computing Machinery}, title = {{Smoothed analysis for graph isomorphism}}, doi = {10.1145/3717823.3718173}, year = {2025}, } @article{20320, abstract = {The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most 2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in one pseudoforest F the components of F have at most d edges. This was proven in 2020 in Grout and Moore (2020). We strengthen this theorem by showing that we can find such a decomposition where additionally F is acyclic, the diameter of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ + 1 if d ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N, we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter bounds are best possible as an extension for both the Strong Nine Dragon Tree Conjecture for pseudoforests and its original conjecture for forests. In fact, they are still optimal even if we only enforce F to have any constant maximum degree, instead of enforcing every component of F to have at most d edges.}, author = {Mies, Sebastian and Moore, Benjamin and Smith-Roberge, Evelyne}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, number = {12}, publisher = {Elsevier}, title = {{Beyond the pseudoforest strong Nine Dragon Tree theorem}}, doi = {10.1016/j.ejc.2025.104214}, volume = {130}, year = {2025}, } @article{20504, abstract = {Let r, k, be integers such that 0 ≤ ≤ (k/r). Given a large r-uniform hypergraph G, we consider the fraction of k-vertex subsets that span exactly edges. If is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than 1. In this paper we prove an essentially optimal result along these lines: if is not 0 or (k/r), then this fraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r, k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when is far from 0 and (k/r).}, author = {Jain, Vishesh and Kwan, Matthew Alan and Mubayi, Dhruv and Tran, Tuan}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {18}, publisher = {Oxford University Press}, title = {{The edge-statistics conjecture for hypergraphs}}, doi = {10.1093/imrn/rnaf273}, volume = {2025}, year = {2025}, } @article{18157, abstract = {Interest in sliding block puzzles dates back to the 15-puzzle, seemingly invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating history of the puzzle). The game consists of fifteen movable square blocks numbered and arranged within a square box, leaving one empty space (see Figure 1). The task at hand is to start from a given configuration of the numbered blocks and reach the desired target configuration, where the only allowed move is to slide a numbered block into an adjacent empty space. This task seemed to be unpredictably either very easy to accomplish, or completely impossible, and the puzzle turned into a worldwide sensation in the spring of 1880. A particularly challenging instance, known as the 13-15-14 puzzle, consisted of initial and target configurations that differed by a single swap (historically this swap involved the blocks labeled 14 and 15). The craze of this puzzle was such that it consistently made newspaper headlines in 1880, with an article in the New York Times lamenting that it was “threatening our free institutions” [23, p. 9]. Various prizes were offered for anyone who could solve this challenge, beginning with a $25 set of teeth and culminating with Sam Loyd’s famous $1,000 cash prize.}, author = {Brunck, Florestan R and Kwan, Matthew Alan}, issn = {0343-6993}, journal = {Mathematical Intelligencer}, pages = {52--65}, publisher = {Springer Nature}, title = {{Books, Hallways, and social butterflies: A note on sliding block puzzles}}, doi = {10.1007/s00283-024-10358-x}, volume = {47}, year = {2025}, } @article{15163, abstract = {For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs.}, author = {Campbell, Rutger and Hörsch, Florian and Moore, Benjamin}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {6}, publisher = {Elsevier}, title = {{Decompositions into two linear forests of bounded lengths}}, doi = {10.1016/j.disc.2024.113962}, volume = {347}, year = {2024}, } @article{18559, abstract = {We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab and Simkin, Michael}, issn = {1939-8980}, journal = {Annals of Mathematics}, number = {3}, pages = {1059--1156}, publisher = {Princeton University}, title = {{High-girth Steiner triple systems}}, doi = {10.4007/annals.2024.200.3.4}, volume = {200}, year = {2024}, } @article{18583, abstract = {There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as . As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two non-empty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a personality-changing scheme: we ‘forget’ certain information based on the state of a Markov chain, giving us more independence to work with.}, author = {Anastos, Michael and Cooley, Oliver and Kang, Mihyun and Kwan, Matthew Alan}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {6}, publisher = {Wiley}, title = {{Partitioning problems via random processes}}, doi = {10.1112/jlms.70010}, volume = {110}, year = {2024}, } @article{18655, abstract = {Let Qd be the d-dimensional binary hypercube. We say that P={v1,…,vk} is an increasing path of length k−1 in Qd, if for every i∈[k−1] the edge vivi+1 is obtained by switching some zero coordinate in vi to a one coordinate in vi+1. Form a random subgraph Qdp by retaining each edge in E(Qd) independently with probability p. We show that there is a phase transition with respect to the length of a longest increasing path around p=ed. Let α be a constant and let p=αd. When αe, whp there is a path of length d−2 in Qdp, and in fact, whether it is of length d−2,d−1, or d depends on whether the all-zero and all-one vertices percolate or not.}, author = {Anastos, Michael and Diskin, Sahar and Elboim, Dor and Krivelevich, Michael}, issn = {1083-589X}, journal = {Electronic Communications in Probability}, publisher = {Duke University Press}, title = {{Climbing up a random subgraph of the hypercube}}, doi = {10.1214/24-ECP639}, volume = {29}, year = {2024}, } @inproceedings{18702, abstract = {In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. }, author = {Anastos, Michael and Auerbach, Benedikt and Baig, Mirza Ahad and Cueto Noval, Miguel and Kwan, Matthew Alan and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z}, booktitle = {22nd International Conference on Theory of Cryptography}, isbn = {9783031780103}, issn = {1611-3349}, location = {Milan, Italy}, pages = {413--443}, publisher = {Springer Nature}, title = {{The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging}}, doi = {10.1007/978-3-031-78011-0_14}, volume = {15364}, year = {2024}, } @inproceedings{18758, abstract = {MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n).}, author = {Lill, Jonas and Petrova, Kalina H and Weber, Simon}, booktitle = {19th International Symposium on Parameterized and Exact Computation}, isbn = {9783959773539}, issn = {1868-8969}, location = {Egham, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound}}, doi = {10.4230/LIPIcs.IPEC.2024.2}, volume = {321}, year = {2024}, } @article{18951, abstract = {We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] d . These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on [n] d features order n d−2 alternating cycles of length at most 4d−2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension d is ergodic when switching alternating cycles of length at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and Rémila, which also uses 8-cycles. None of our proofs make reference to height functions.}, author = {Hartarsky, Ivailo and Lichev, Lyuben and Toninelli, Fabio Lucio}, issn = {2308-5835}, journal = {Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions}, publisher = {EMS Press}, title = {{Local dimer dynamics in higher dimensions}}, doi = {10.4171/aihpd/200}, year = {2024}, } @article{17376, abstract = {The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number α(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible. While there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n-vertex graph for which even the unweighted ratio bound can prove α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.}, author = {Kwan, Matthew Alan and Wigderson, Yuval}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {10}, pages = {3196--3208}, publisher = {London Mathematical Society}, title = {{The inertia bound is far from tight}}, doi = {10.1112/blms.13127}, volume = {56}, year = {2024}, } @article{17475, abstract = {As a discrete analogue of Kac’s celebrated question on ‘hearing the shape of a drum’ and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that ‘almost all graphs are determined by their spectrum’, meaning that the fraction of unlabelled n-vertex graphs which are determined by their spectrum converges to 1 as n → ∞. In this paper, we make a step towards this conjecture, showing that there are exponentially many n-vertex graphs which are determined by their spectrum. This improves on previous bounds (of shape e c √ n ). We also propose a number of further directions of research. }, author = {Koval, Illya and Kwan, Matthew Alan}, issn = {1464-3847}, journal = {Quarterly Journal of Mathematics}, number = {3}, pages = {869--899}, publisher = {Oxford University Press}, title = {{Exponentially many graphs are determined by their spectrum}}, doi = {10.1093/qmath/haae030}, volume = {75}, year = {2024}, } @article{11706, abstract = {We say that (Formula presented.) if, in every edge coloring (Formula presented.), we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy of (Formula presented.). The well-known states that the threshold for the property (Formula presented.) is equal to (Formula presented.), where (Formula presented.) is given by (Formula presented.) for any pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.). In this article, we show the 0-statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques. }, author = {Liebenau, Anita and Mattos, Letícia and Mendonca Dos Santos, Walner and Skokan, Jozef}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {4}, pages = {1035--1055}, publisher = {Wiley}, title = {{Asymmetric Ramsey properties of random graphs involving cliques and cycles}}, doi = {10.1002/rsa.21106}, volume = {62}, year = {2023}, } @article{13042, abstract = {Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant. We show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s. for c>20, thus extending a result of Frieze and the author to smaller values of c. Thereafter, for c>20, we determine the limit of the probability that G(n, c/n)contains cycles of every length between the length of its shortest and its longest cycles as n→∞.}, author = {Anastos, Michael}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, number = {2}, publisher = {Electronic Journal of Combinatorics}, title = {{A note on long cycles in sparse random graphs}}, doi = {10.37236/11471}, volume = {30}, year = {2023}, } @article{14319, abstract = {We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We also make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour multiplicities.}, author = {Anastos, Michael and Fabian, David and Müyesser, Alp and Szabó, Tibor}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, number = {3}, publisher = {Electronic Journal of Combinatorics}, title = {{Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets}}, doi = {10.37236/11714}, volume = {30}, year = {2023}, } @inproceedings{14344, abstract = {We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting.}, author = {Anastos, Michael}, booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611977554}, location = {Florence, Italy}, pages = {2286--2323}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fast algorithms for solving the Hamilton cycle problem with high probability}}, doi = {10.1137/1.9781611977554.ch88}, volume = {2023}, year = {2023}, } @article{14444, abstract = {We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN , where N is the number of intercalates in a uniformly random order- n Latin square. In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order- n Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices with the same arrangement of symbols) is of order n4, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab and Simkin, Michael}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {363--416}, publisher = {Springer Nature}, title = {{Substructures in Latin squares}}, doi = {10.1007/s11856-023-2513-9}, volume = {256}, year = {2023}, }