@article{21884, abstract = {We show that a randomly perturbed digraph, where we start with a dense digraph Dα and add a small number of random edges to it, will typically contain a fixed orientation of a bounded-degree spanning tree. This answers a question posed by Araujo, Balogh, Krueger, Piga and Treglown and generalizes the corresponding result for randomly perturbed graphs by Krivelevich, Kwan and Sudakov. More specifically, we prove that there exists a constant c=c(α,Δ) such that if T is an oriented tree with maximum degree Δ and Dα is an n-vertex digraph with minimum semidegree αn, then the graph obtained by adding cn uniformly random edges to Dα will contain T with high probability.}, author = {Morawski, Patryk and Petrova, Kalina H}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, number = {2}, publisher = {Electronic Journal of Combinatorics}, title = {{Randomly perturbed digraphs also have bounded-degree spanning trees}}, doi = {10.37236/13316}, volume = {33}, year = {2026}, } @article{20422, abstract = {We show that if n is odd and p>=Clog n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space. }, author = {Christoph, Micha and Nenadov, Rajko and Petrova, Kalina H}, issn = {1096-0902}, journal = {Journal of Combinatorial Theory Series B}, pages = {254--267}, publisher = {Elsevier}, title = {{The Hamilton space of pseudorandom graphs}}, doi = {10.1016/j.jctb.2025.09.002}, volume = {176}, year = {2026}, } @article{20482, abstract = {In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs H in Kn, defined as the minimum number of colours needed to colour the edges of K so that every copy of a graph H E H intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when H is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies, that is, {Kt,n-t : t E T} for a fixed set of integers T c [[n/2]]. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs.}, author = {Boyadzhiyska, Simona and Das, Shagnik and Lesgourgues, Thomas and Petrova, Kalina H}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Odd-Ramsey numbers of complete bipartite graphs}}, doi = {10.1016/j.ejc.2025.104235}, volume = {131}, year = {2026}, } @article{21159, abstract = {One of the foundational theorems of extremal graph theory is Dirac’s theorem, which says that if an n-vertex graph G has minimum degree at least n/2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k, and for n divisible by k, let md (k, n) be the minimum d-degree that ensures the existence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of md (k, n), but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n) (for any constantγ > 0), then the number of perfect matchings in G is controlled by an entropy-like parameter of G. This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.}, author = {Kwan, Matthew Alan and Safavi Hemami, Roodabeh and Wang, Yiting}, issn = {1439-6912}, journal = {Combinatorica}, publisher = {Springer Nature}, title = {{Counting perfect matchings in Dirac hypergraphs}}, doi = {10.1007/s00493-025-00194-8}, volume = {46}, year = {2026}, } @article{21706, abstract = {Consider a quadratic polynomial Q(ξ1, . . . , ξn) of independent Rademacher random variables ξ1, . . . , ξn. To what extent can Q(ξ1, . . . , ξn) concentrate on a single value? This quadratic version of the classical Littlewood–Offord problem was popularised by Costello, Tao and Vu in their study of symmetric random matrices. In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if Q(ξ1, . . . , ξn) ‘robustly depends on at least m of the ξi’ in the sense that there is no way to pin down the value of Q(ξ1, . . . , ξn) by fixing values for fewer than m of the variables ξi, then we have Pr[Q(ξ1, . . . , ξn) = 0] ≤ O(1/√m). This also implies a similar result in the case where ξ1, . . . , ξn have arbitrary distributions. Our proof combines a number of ideas that may be of independent interest, including an inductive decoupling scheme that reduces quadratic anticoncentration problems to high-dimensional linear anticoncentration problems. Also, one application of our main result is the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related to graph inducibility. }, author = {Kwan, Matthew Alan and Sauermann, Lisa}, issn = {1570-5846}, journal = {Compositio Mathematica}, number = {12}, pages = {3089--3139}, publisher = {Cambridge University Press}, title = {{Resolution of the quadratic Littlewood–Offord problem}}, doi = {10.1112/S0010437X25102789}, volume = {161}, year = {2025}, } @article{19418, abstract = {The size-Ramsey number r^(H) of a graph H is the smallest number of edges a (host) graph G can have, such that for any red/blue colouring of G, there is a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that if H is a graph on n vertices and maximum degree three, then r^(H)=O(n8/5), improving upon the upper bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi. In this paper we show that r^(H)≤n3/2+o(1). While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.}, author = {Draganić, Nemanja and Petrova, Kalina H}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {3}, publisher = {Wiley}, title = {{Size‐Ramsey numbers of graphs with maximum degree three}}, doi = {10.1112/jlms.70116}, volume = {111}, year = {2025}, } @article{19433, abstract = {An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of r-dimensional orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case r≥3 much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain.}, author = {Anastos, Michael and Jin, Zhihan and Kwan, Matthew Alan and Sudakov, Benny}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Extremal, enumerative and probabilistic results on ordered hypergraph matchings}}, doi = {10.1017/fms.2024.144}, volume = {13}, year = {2025}, } @article{19440, abstract = {Let μ(G) denote the minimum number of edges whose addition to G results in a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n. Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability, μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p) and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability, the algorithm returns a set of edges of size μ(G) whose addition to G results in a pancyclic (and therefore also Hamiltonian) graph.}, author = {Alon, Yahav and Anastos, Michael}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {2}, publisher = {Wiley}, title = {{The completion numbers of hamiltonicity and pancyclicity in random graphs}}, doi = {10.1002/rsa.21286}, volume = {66}, year = {2025}, } @article{19503, abstract = {A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers s,t≥1 there exists a finite number F(s,t) such that the vertex set of every digraph of minimum out-degree at least F(s,t) can be partitioned into non-empty parts A and B such that the subdigraphs induced on A and B have minimum out-degree at least s and t , respectively. In this short note, we prove that if F(2,2) exists, then all the numbers F(s,t) with s,t≥1 exist and satisfy F(s,t)=Θ(s+t) . In consequence, the problem of Alon and Stiebitz reduces to the case s=t=2 . Moreover, the numbers F(s,t) with s,t≥2 either all exist and grow linearly, or all of them do not exist.}, author = {Christoph, Micha and Petrova, Kalina H and Steiner, Raphael}, issn = {1469-2163}, journal = {Combinatorics Probability and Computing}, number = {4}, pages = {559--564}, publisher = {Cambridge University Press}, title = {{A note on digraph splitting}}, doi = {10.1017/S0963548325000045}, volume = {34}, year = {2025}, } @article{19508, abstract = {We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree (that does not fall into the previous class of graphs), we show convergence at a double-exponential rate.}, author = {Attia, Luc and Lichev, Lyuben and Mitsche, Dieter and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, issn = {2153-0793}, journal = {Dynamic Games and Applications}, pages = {1517--1535}, publisher = {Springer Nature}, title = {{Random zero-sum dynamic games on infinite directed graphs}}, doi = {10.1007/s13235-025-00636-4}, volume = {15}, year = {2025}, } @article{19554, abstract = {In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation of the differential equation method (comparing the so-called Karp–Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph.}, author = {Glasgow, Margalit and Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {4}, publisher = {Wiley}, title = {{A central limit theorem for the matching number of a sparse random graph}}, doi = {10.1112/jlms.70101}, volume = {111}, year = {2025}, } @article{19603, abstract = {MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famousEdwards-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 weight at least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF (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}, issn = {1432-0541}, journal = {Algorithmica}, pages = {983--1007}, publisher = {Springer Nature}, title = {{Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound}}, doi = {10.1007/s00453-025-01306-y}, volume = {87}, year = {2025}, } @article{19798, abstract = {In an n×n array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than βn times, the array contains a transversal of size (1−β/4−o(1))n . In particular, if the array is filled with n symbols, each appearing n times (an equi- n square), we get transversals of size (3/4−o(1))n. Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals.}, author = {Anastos, Michael and Morris, Patrick}, issn = {1520-6610}, journal = {Journal of Combinatorial Designs}, number = {9}, pages = {338--342}, publisher = {Wiley}, title = {{A note on finding large transversals efficiently}}, doi = {10.1002/jcd.21990}, volume = {33}, year = {2025}, } @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{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{18478, abstract = {For a given graph G=(V,E), we define its \emph{nth subdivision} as the graph obtained from G by replacing every edge by a path of length n. We also define the \emph{mth power} of G as the graph on vertex set V where we connect every pair of vertices at distance at most m in G. In this paper, we study the chromatic number of powers of subdivisions of graphs and resolve the case m=n asymptotically. In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in the case m=n=3 in a strong sense.}, author = {Anastos, Michael and Boyadzhiyska, Simona and Rathke, Silas and Rué, Juanjo}, issn = {0166-218X}, journal = {Discrete Applied Mathematics}, pages = {506--511}, publisher = {Elsevier}, title = {{On the chromatic number of powers of subdivisions of graphs}}, doi = {10.1016/j.dam.2024.10.002}, volume = {360}, year = {2025}, } @article{18753, abstract = {We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs C, a hero in C is any digraph H such that H -free digraphs in C have bounded dichromatic number. We show that if F is an oriented star of degree at least five, the only heroes for the class of F -free digraphs are transitive tournaments. For oriented stars F of degree exactly four, we show the only heroes in F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two "valid" orientations of brooms, then every transitive tournament is a hero for this class of digraphs.}, author = {Carbonero, Alvaro and Koerts, Hidde and Moore, Benjamin and Spirkl, Sophie}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{On heroes in digraphs with forbidden induced forests}}, doi = {10.1016/j.ejc.2024.104104}, volume = {125}, year = {2025}, }