Search

A seminal result of Koml\'os, S\'ark\"ozy, and Szemer\'edi states that any n-vertex graph G with minimum degree at least (1/2 + {\alpha})n contains every n-vertex tree T of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result to show that such graphs G in fact support an optimally spread distribution on copies of a given T, which implies, using the recent breakthroughs on the Kahn-Kalai conjecture, the robustness result that T is a subgraph of sparse random subgraphs of G as well. Pham, Sah, Sawhney, and Simkin construct their optimally spread distribution by following closely the original proof of the Koml\'os-S\'ark\"ozy-Szemer\'edi theorem which uses the blow-up lemma and the Szemer\'edi regularity lemma. We give an alternative, regularity-free construction that instead uses the Koml\'os-S\'ark\"ozy-Szemer\'edi theorem (which has a regularity-free proof due to Kathapurkar and Montgomery) as a black-box. Our proof is based on the simple and general insight that, if G has linear minimum degree, almost all constant sized subgraphs of G inherit the same minimum degree condition that G has., Comment: 12 pages

An $\ell$-lift of a graph $G$ is any graph obtained by replacing every vertex of $G$ with an independent set of size $\ell$, and connecting every pair of two such independent sets that correspond to an edge in $G$ by a matching of size $\ell$. Graph lifts have found numerous interesting applications and connections to a variety of areas over the years. Of particular importance is the random graph model obtained by considering an $\ell$-lift of a graph sampled uniformly at random. This model was first introduced by Amit and Linial in 1999, and has been extensively investigated since. In this paper, we study the size of the largest topological clique in random lifts of complete graphs. In 2006, Drier and Linial raised the conjecture that almost all $\ell$-lifts of the complete graph on $n$ vertices contain a subdivision of a clique of order $\Omega(n)$ as a subgraph provided $\ell$ is at least linear in $n$. We confirm their conjecture in a strong form by showing that for $\ell \ge (1+o(1))n$, one can almost surely find a subdivision of a clique of order $n$. We prove that this is tight by showing that for $\ell \le (1-o(1))n$, almost all $\ell$-lifts do not contain subdivisions of cliques of order $n$. Finally, for $2 \le \ell \ll n$, we show that almost all $\ell$-lifts of $K_n$ contain a subdivision of a clique on $(1-o(1))\sqrt{\frac{2n \ell}{1-1/\ell}}$ vertices and that this is tight up to the lower order term.

We show that a $k$-uniform hypergraph on $n$ vertices has a spanning subgraph homeomorphic to the $(k - 1)$-dimensional sphere provided that $H$ has no isolated vertices and each set of $k - 1$ vertices supported by an edge is contained in at least $n/2 + o(n)$ edges. This gives a topological extension of Dirac's theorem and asymptotically confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery, and Narayanan. Unlike typical results in the area, our proof does not rely on the Absorption Method, the Regularity Lemma or the Blow-up Lemma. Instead, we use a recently introduced framework that is based on covering the vertex set of the host graph with a family of complete blow-ups., Comment: 20 pages

We show that the edges of any $d$-regular graph can be almost decomposed into paths of length roughly $d$, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a $d$-regular graph can be partitioned into $n/(d+1)$ paths, asymptotically confirming a conjecture of Magnant and Martin from 2009., Comment: 34 pages, 1 figure

We show that $(n,d,\lambda)$-graphs with $\lambda=O(d/\log^3 n)$ are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang of the form $\lambda=d/\exp{(O(\sqrt{\log n}))}$, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. Our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Koml\'os and Szemer\'edi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance., Comment: 15 pages, 3 figures

Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to randomly embed $G$ into $H$ with good "spread". More precisely, for a wide class of $G$, we find a randomised embedding $f\colon G\hookrightarrow H$ with the following property: for every $s$, for any partial embedding $f'$ of $s$ vertices of $G$ into $H$, the probability that $f$ extends $f'$ is at most $O(1/n)^s$. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem. For example, setting $s=n$, we obtain an asymptotically tight lower bound on the number of embeddings of $G$ into $H$. This recovers and extends recent results of Glock, Gould, Joos, K\"uhn, and Osthus and of Montgomery and Pavez-Sign\'e regarding enumerating Hamilton cycles in Dirac hypergraphs. Moreover, using the recent developments surrounding the Kahn--Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning $G$ still embeds into $H$ after a random sparsification of its edge set. This allows us to recover a recent result of Kang, Kelly, K\"uhn, Osthus, and Pfenninger and of Pham, Sah, Sawhney, and Simkin for perfect matchings, and obtain novel results for Hamilton cycles and factors in Dirac hypergraphs. Notably, our randomised embedding algorithm is self-contained and does not require Szemer\'edi's regularity lemma or iterative absorption.

An orthomorphism of a finite group $G$ is a bijection $\phi\colon G\to G$ such that $g\mapsto g^{-1}\phi(g)$ is also a bijection. In 1981, Friedlander, Gordon, and Tannenbaum conjectured that when $G$ is abelian, for any $k\geq 2$ dividing $|G|-1$, there exists an orthomorphism of $G$ fixing the identity and permuting the remaining elements as products of disjoint $k$-cycles. We prove this conjecture for all sufficiently large groups., Comment: 34 pages

We study multigraphs whose edge-sets are the union of three perfect matchings, $M_1$, $M_2$, and $M_3$. Given such a graph $G$ and any $a_1,a_2,a_3\in \mathbb{N}$ with $a_1+a_2+a_3\leq n-2$, we show there exists a matching $M$ of $G$ with $|M\cap M_i|=a_i$ for each $i\in \{1,2,3\}$. 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.

Given a collection of hypergraphs $\textbf{H}=(H_1,\ldots,H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\textbf{H}$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim [Bull. Lond. Math. Soc., 2020, 52(3):498-504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P\'osa-Seymour conjecture., Comment: 21 pages, 4 figures; final version as accepted for publication in the Bulletin of the London Mathematical Society

Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? In this paper, we investigate this question and its multicolour variant. For instance, we show that any such graph contains a $t$-blow-up of an \textit{alternating 4-cycle} with $t = \Omega(\log n)$., Comment: Improved exposition

A complete mapping of a group $G$ is a bijection $\phi\colon G\to G$ such that $x\mapsto x\phi(x)$ is also bijective. Hall and Paige conjectured in 1955 that a finite group $G$ has a complete mapping whenever $\prod_{x\in G} x$ is the identity in the abelianization of $G$. This was confirmed in 2009 by Wilcox, Evans, and Bray with a proof using the classification of finite simple groups. \par In this paper, we give a combinatorial proof of a far-reaching generalisation of the Hall-Paige conjecture for large groups. We show that for random-like and equal-sized subsets $A,B,C$ of a group $G$, there exists a bijection $\phi\colon A\to B$ such that $x\mapsto x\phi(x)$ is a bijection from $A$ to $C$ whenever $\prod_{a\in A} a \prod_{b\in B} b=\prod_{c\in C} c$ in the abelianization of $G$. We use this statement as a black-box to settle the following old problems in combinatorial group theory for large groups. (1) We characterise sequenceable groups, that is, groups which admit a permutation $\pi$ of their elements such that the partial products $\pi_1$, $\pi_1\pi_2$, $\pi_1\pi_2\cdots \pi_n$ are all distinct. This resolves a problem of Gordon from 1961 and confirms conjectures made by several authors, including Keedwell's 1981 conjecture that all large non-abelian groups are sequenceable. We also characterise the related $R$-sequenceable groups, addressing a problem of Ringel from 1974. (2) We confirm in a strong form a conjecture of Snevily from 1999 by characterising large subsquares of multiplication tables of finite groups that admit transversals. Previously, this characterisation was known only for abelian groups of odd order (by a combination of papers by Alon and Dasgupta-K\'arolyi-Serra-Szegedy and Arsovski)., Comment: Major revision including resolution of several additional conjectures regarding sequenceable groups

Given a collection of graphs $\mathbf{G}=(G_1, \ldots, G_m)$ with the same vertex set, an $m$-edge graph $H\subset \cup_{i\in [m]}G_i$ is a transversal if there is a bijection $\phi:E(H)\to [m]$ such that $e\in E(G_{\phi(e)})$ for each $e\in E(H)$. We give asymptotically-tight minimum degree conditions for a graph collection on an $n$-vertex set to have a transversal which is a copy of a graph $H$, when $H$ is an $n$-vertex graph which is an $F$-factor or a tree with maximum degree $o(n/\log n)$., Comment: 21 pages

Suppose that $R$ (red) and $B$ (blue) are two graphs on the same vertex set of size $n$, and $H$ is some graph with a red-blue coloring of its edges. How large can $R$ and $B$ be if $R\cup B$ does not contain a copy of $H$? Call the largest such integer $\mathrm{mex}(n, H)$. This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when $H$ is a complete graph on $k+1$ vertices with any coloring of its edges $\mathrm{mex}(n,H)=\mathrm{ex}(n, K_{k+1})$. This conjecture generalizes Tur\'an's theorem. Diwan and Mubayi also asked for an analogue of Erd\H{o}s-Stone-Simonovits theorem in this context. We prove the following asymptotic characterization of the extremal threshold in terms of the chromatic number $\chi(H)$ and the \textit{reduced maximum matching number} $\mathcal{M}(H)$ of $H$. $$\mathrm{mex}(n, H)=\left(1- \frac{1}{2(\chi(H)-1)} - \Omega\left(\frac{\mathcal{M}(H)}{\chi(H)^2}\right)\right)\frac{n^2}{2}.$$ $\mathcal{M}(H)$ is, among the set of proper $\chi(H)$-colorings of $H$, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than $2$ colors and is tight up to the implied constant factor. We also study $\mathrm{mex}(n, H)$ when $H$ is a cycle with a red-blue coloring of its edges, and we show that $\mathrm{mex}(n, H)\lesssim \frac{1}{2}\binom{n}{2}$, which is tight.

We study Tur\'an and Ramsey-type problems on edge-colored graphs. An edge-colored graph is called {\em $\varepsilon$-balanced} if each color class contains at least an $\varepsilon$-proportion of its edges. Given a family $\mathcal{F}$ of edge-colored graphs, the Ramsey function $R(\varepsilon, \mathcal{F})$ is the smallest $n$ for which any $\varepsilon$-balanced $K_n$ must contain a copy of an $F\in\mathcal{F}$, and the Tur\'an function $\mathrm{ex}(\varepsilon, n, \mathcal{F})$ is the maximum number of edges in an $n$-vertex $\varepsilon$-balanced graph which avoids all of $\mathcal{F}$. In this paper, we consider this Tur\'an function for several classes of edge-colored graphs, we show that the Ramsey function is linear for bounded degree graphs, and we prove a theorem that gives a relationship between the two parameters.

We study a Tur\'an-type problem on edge-colored complete graphs. We show that for any $r$ and $t$, any sufficiently large $r$-edge-colored complete graph on $n$ vertices with $\Omega(n^{2-1/tr^r})$ edges in each color contains a member from certain finite family $\mathcal{F}_t^r$ of $r$-edge-colored complete graphs. We conjecture that $\Omega(n^{2-1/t})$ edges in each color are sufficient to find a member from ${\mathcal{F}}_t^r$. A result of Gir\~ao and Narayanan confirms this conjecture when $r=2$. Next, we study a related problem where the corresponding Tur\'an threshold is linear. We call an edge-coloring of a path $P_{rk}$ balanced if each color appears $k$ times in the coloring. We show that any $3$-edge-coloring of a large complete graph with $kn+o(n)$ edges in each color contains a balanced $P_{3k}$. This is tight up to a constant factor of $2$. For more colors, the problem becomes surprisingly more delicate. Already for $r=7$, we show that even $n^{2-o(1)}$ edges from each color does not guarantee existence of a balanced $P_{7k}$., Comment: 17 pages, 1 figure

We provide multicolored and infinite generalizations for a Ramsey-type problem raised by Bollob\'as, concerning colorings of $K_n$ where each color is well-represented. Let $\chi$ be a coloring of the edges of a complete graph on $n$ vertices into $r$ colors. We call $\chi$ $\varepsilon$-balanced if all color classes have $\varepsilon$ fraction of the edges. Fix some graph $H$, together with an $r$-coloring of its edges. Consider the smallest natural number $R_\varepsilon^r(H)$ such that for all $n\geq R_\varepsilon^r(H)$, all $\varepsilon$-balanced colorings $\chi$ of $K_n$ contain a subgraph isomorphic to $H$ in its coloring. Bollob\'as conjectured a simple characterization of $H$ for which $R_\varepsilon^2(H)$ is finite, which was later proved by Cutler and Mont\'agh. Here, we obtain a characterization for arbitrary values of $r$, as well as asymptotically tight bounds. We also discuss generalizations to graphs defined on perfect Polish spaces, where the corresponding notion of balancedness is each color class being non-meagre.