Alexey Pokrovskiy

A variant of the Erdős–Sós conjecture, posed by Havet, Reed, Stein and Wood, states that every graph with minimum degree at least and maximum degree at least contains a copy of every tree with edges. Both degree bounds are best possible. We confirm this conjecture for large trees with bounded maximum degree, by proving that for all and sufficiently large , every graph with and contains a copy of every tree with edges and . We also prove similar results where alternative degree conditions are considered. For the same class of trees, this verifies exactly a related conjecture of Besomi, Pavez‐Signé and Stein, and provides asymptotic confirmations of two others.

Ryser conjectured that every ‐edge‐coloured complete graph can be covered by monochromatic trees. Motivated by a question of Austin in analysis, Milićević predicted something stronger — that every ‐edge‐coloured complete graph can be covered by monochromatic trees of bounded diameter . Here we show that the two conjectures are equivalent. As immediate corollaries we obtain new results about Milićević's Conjecture, most notably that it is true for . We also obtain several new cases of a generalization of Milićević's Conjecture to non‐complete graphs due to DeBiasio–Kamel–McCourt–Sheats.

A Latin square of order n n is an n × n n \times n array filled with n n symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser-Brualdi-Stein from 60s which says that every Latin square of order n × n n\times n contains a transversal of order n − 1 n-1 . In this paper we prove the existence of a transversal of order n − O ( log ⁡ n / log ⁡ log ⁡ n ) n-O(\log {n}/\log {\log {n}}) , improving the celebrated bound of n − O ( log 2 ⁡ n ) n-O(\log ^2n) by Hatami and Shor. Our approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. We obtain a new lower bound on a 40-year-old conjecture of Brouwer on the maximum matching in Steiner triple systems, showing that every such system of order n n is guaranteed to have a matching of size n / 3 − O ( log ⁡ n / log ⁡ log ⁡ n ) n/3-O(\log {n}/\log {\log {n}}) . This substantially improves the current best result of Alon, Kim and Spencer which has the error term of order n 1 / 2 + o ( 1 ) n^{1/2+o(1)} . Finally, we also show that O ( n log ⁡ n / log ⁡ log ⁡ n ) O(n\log {n}/\log {\log {n}}) many symbols in Latin arrays suffice to guarantee a full transversal, improving on a previously known bound of n 2 − ε n^{2-\varepsilon } . The proofs combine in a novel way the semi-random method together with the robust expansion properties of edge-coloured pseudorandom graphs to show the existence of a rainbow matching covering all but O ( log ⁡ n / log ⁡ log ⁡ n ) O(\log n/\log {\log {n}}) vertices. All previous results, based on the semi-random method, left uncovered at least Ω ( n α ) \Omega (n^{\alpha }) (for some constant α > 0 \alpha >0 ) vertices.

Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.