@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{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{22147, abstract = {Let 1 ≤ k ≤ n and M be a random n × n matrix with independent uniformly random {±1}-entries. We show that there exists an absolute constant c > 0 such that P[rank(M) ≤ n − k] ≤ exp(−cnk). This confirms a well-known prediction in the area, extending a result of Rudelson (who previously proved this same result under the restriction k ≤ √n, via different methods).}, author = {Hunter, Zach and Kwan, Matthew Alan and Sauermann, Lisa and Sawhney, Mehtaab}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {12}, publisher = {Oxford University Press}, title = {{On random matrices with large corank}}, doi = {10.1093/imrn/rnag126}, volume = {2026}, year = {2026}, } @article{22752, abstract = {In this note we outline a new and simple approach to proving central limit theorems for various ‘global’ graph parameters that have robust ‘local’ approximations, using the Efron–Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the 𝑘 -core for sparse random graphs.}, author = {Anastos, Michael and Erde, Joshua and Kang, Mihyun and Pfenninger, Vincent}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {8}, publisher = {Wiley}, title = {{A short proof of a central limit theorem for the order of the giant component and k-core}}, doi = {10.1112/blms.70464}, volume = {58}, year = {2026}, } @article{22813, abstract = {Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state |ψ. Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform |ψ into another state |φ. Famously, Nielsen’s theorem [28] provides a necessary and sufficient algebraic criterion for such a transformation to be possible (namely, the entanglement spectrum of |φ should majorise the entanglement spectrum of |ψ). In the paper where Nielsen proved this theorem, he conjectured that in the limit of large dimensionality, for almost all pairs of states |ψ, |φ (according to the natural unitary invariant measure) such a transformation is not possible. That is to say, typical pairs of quantum states |ψ, |φ are entangled in fundamentally different ways, that cannot be converted to each other via local operations and classical communication.ViaNielsen’s theorem, this conjecture can be equivalently stated as a conjecture about majorisation of spectra of random matrices from the so-called trace-normalised complex Wishart–Laguerre ensemble. Concretely, let X and Y be independent n × m random matrices whose entries are i.i.d. standard complex Gaussians; then Nielsen’s conjecture says that the probability that the spectrum of XX†/ tr(XX†) majorises the spectrum of YY†/ tr(YY†) tends to zero as both n and m grow large. We prove this conjecture, and we also confirm some related predictions of Cunden et al. [12].}, author = {Jain, Vishesh and Kwan, Matthew Alan and Michelen, Marcus}, issn = {1432-0916}, journal = {Communications in Mathematical Physics}, number = {10}, publisher = {Springer}, title = {{Entangled states are typically incomparable}}, doi = {10.1007/s00220-026-05711-4}, volume = {407}, year = {2026}, } @article{23001, abstract = {A famous conjecture by Itai and Zehavi states that, for every 𝑑 -vertex-connected graph 𝐺 and every vertex 𝑟 in 𝐺 , there are 𝑑 spanning trees of 𝐺 such that, for every vertex 𝑣 in 𝐺 ∖{𝑟} , the paths between 𝑟 and 𝑣 in different trees are internally vertex-disjoint. We show that with high probability the Itai–Zehavi conjecture holds asymptotically for the Erdős–Rényi random graph 𝐺⁡(𝑛,𝑝) when 𝑛⁢𝑝 =𝜔⁡(log⁡𝑛) and for random regular graphs 𝐺⁡(𝑛,𝑑) when 𝑑 =𝜔⁡(log⁡𝑛) . Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers a question of Draganić and Krivelevich positively. Our proof makes use of recent developments on sprinkling techniques in random regular graphs.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien and Wang, Yiting}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {2}, publisher = {Wiley}, title = {{Approximate Itai–Zehavi conjecture for random graphs}}, doi = {10.1002/rsa.70095}, volume = {69}, year = {2026}, } @article{23123, abstract = {How many points can be placed in an 𝑛 × 𝑛 grid sothat every (affine) line contains at most 𝑘 points? Weprove that for 𝑛 ⩾ 𝑘 ⩾ 1037 the maximum number ofpoints is exactly 𝑘𝑛. Our proof builds on the recent workof Kovács, Nagy and Szabó (who proved an analogousresult when 𝑘 is at least about √𝑛 log 𝑛), incorporat-ing ideas of Jain and Pham. Using the same approach,we also obtain new bounds for higher-dimensionalextensions of this problem}, author = {Grebennikov, Aleksandr and Kwan, Matthew Alan}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {10}, publisher = {Wiley}, title = {{No‐(k+1)‐in‐line problem for large constant k}}, doi = {10.1112/blms.70510}, volume = {58}, year = {2026}, } @article{23155, abstract = {In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters d1 ≤ d2, there exists a coupling of G(n,d1) and G(n,d2) satisfying that G(n,d1) ⊆ G(n,d2) with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime. Our contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for generating unions of random edge-disjoint perfect matchings, and refined estimates of Gao’s bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev, McKay, Southwell and Zhukovskii.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien and Wang, Yiting}, issn = {2168-8737}, journal = {Annals of Applied Probability}, keywords = {Random regular graphs, coupling, contiguity, total variation distance, decomposition}, number = {5}, pages = {4716--4738}, publisher = {Institute of Mathematical Statistics}, title = {{Monotonicity and decompositions of random regular graphs}}, doi = {10.1214/26-AAP2345}, volume = {36}, year = {2026}, } @article{23158, abstract = {For a tree T and a function f:E(T)→Sd, the imbalance of a subtree T′⊆T is given by |∑e∈E(T′)f(e)|. The d-dimensional discrepancy of the tree T is the minimum, over all functions f as above, of the maximum imbalance of a subtree of T. We prove tight asymptotic bounds for the discrepancy of a tree T, confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. We also settle a related conjecture on oriented discrepancy of subtrees by the same authors.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, keywords = {Trees, High-dimensional discrepancy, Oriented discrepancy}, publisher = {Springer}, title = {{A note on high-dimensional discrepancy of subtrees}}, doi = {10.1007/s00454-025-00790-x}, year = {2026}, } @unpublished{21211, abstract = {We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such that every nvertex d-regular graph with d ≥ d0 has a collection of vertex-disjoint F-subdivisions covering at least (1 − η)n vertices. This verifies a conjecture of Verstraëte from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required d to be at least polylogarithmic in n. }, author = {Montgomery, Richard and Petrova, Kalina H and Ranganathan, Arjun and Tan, Jane}, booktitle = {arXiv}, title = {{Packing subdivisions into regular graphs}}, doi = {10.48550/arXiv.2508.00480}, year = {2025}, } @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{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{19002, abstract = {A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such that the set of vertices coloured i induce a disjoint union of cliques. The subchromatic number, χsub(G), is the minimum k such that G admits a k-subcolouring. Nešetril, ˇ Ossona de Mendez, Pilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for χsub(G2) when G is planar. We show that χsub(G2) ≤ 43 when G is planar, improving their bound of 135. We give even better bounds when the planar graph G has larger girth. Moreover, we show that χsub(G3) ≤ 95, improving the previous bound of 364. For these we adapt some recent techniques of Almulhim and Kierstead (2022), while also extending the decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez, Quiroz, Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that these decompositions are the precursors of the graph product structure theorem of planar graphs. We give improved bounds for χsub(Gp) for all p ≥ 2, whenever G has bounded treewidth, bounded simple treewidth, bounded genus, or excludes a clique or biclique as a minor. For this we introduce a family of parameters which form a gradation between the strong and the weak colouring numbers. We give upper bounds for these parameters for graphs coming from such classes. Finally, we give a 2-approximation algorithm for the subchromatic number of graphs having a layering in which each layer has bounded cliquewidth and this layering is computable in polynomial time (like the class of all dth powers of planar graphs, for fixed d). This algorithm works even if the power p and the graph G is unknown.}, author = {Cortés, Pedro P. and Kumar, Pankaj and Moore, Benjamin and Ossona de Mendez, Patrice and Quiroz, Daniel A.}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {4}, publisher = {Elsevier}, title = {{Subchromatic numbers of powers of graphs with excluded minors}}, doi = {10.1016/j.disc.2024.114377}, volume = {348}, year = {2025}, } @article{19017, abstract = {Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. Brown, Erdős and Sós [New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan 1971), pp. 53--63, Academic Press 1973] conjectured that the limit limn→∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously determined for k=2 in the original paper of Brown, Erdős and Sós, for k=3 by Glock [Bull. Lond. Math. Soc. 51 (2019) 230--236] and for k=4 by Glock, Joos, Kim, Kühn, Lichev and Pikhurko [arXiv:2209.14177, accepted by Proc. Amer. Math. Soc.] while Delcourt and Postle [arXiv:2210.01105, accepted by Proc. Amer. Math. Soc.] proved the conjecture (without determining the limiting value). In this paper, we determine the value of the limit in the Brown-Erdős-Sós Problem for k∈{5,6,7}. More generally, we obtain the value of limn→∞n−2f(r)(n;rk−2k+2,k) for all r≥3 and k∈{5,6,7}. In addition, by combining these new values with recent results of Bennett, Cushman and Dudek [arXiv:2309.00182] we obtain new asymptotic values for several generalised Ramsey numbers.}, author = {Glock, Stefan and Kim, Jaehoon and Lichev, Lyuben and Pikhurko, Oleg and Sun, Shumin}, issn = {1496-4279}, journal = {Canadian Journal of Mathematics}, pages = {1--43}, publisher = {Cambridge University Press}, title = {{On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7}}, doi = {10.4153/s0008414x25000021}, year = {2025}, } @article{19018, abstract = {The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of their choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalized online semi-random models. We analyse a particular instance that shares similar features with the original semi-random graph process and determine the hitting times of the classical graph properties minimum degree k,k-connectivity, containment of a perfect matching, a Hamiltonian cycle and an H-factor for a fixed graph H possessing an additional tree-like property. Along the way, we derive a few consequences of the famous Aldous-Broder algorithm that may be of independent interest.}, author = {Burova, Sofiya and Lichev, Lyuben}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{The semi-random tree process}}, doi = {10.1016/j.ejc.2025.104120}, volume = {126}, 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}, }