Search

For $2\leq s, Comment: 7 pages

In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lov\'asz theta function of its complement. We combine this with known bounds on the Lov\'asz theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$., Comment: 7 pages

The following natural problem was raised independently by Erdos-Hajnal and Linial-Rabinovich in the early '90 s. How large must the independence number alpha (G) of a graph G be whose every m vertices contain an independent set of size r? In this paper, we discuss new methods to attack this problem. The first new approach, based on bounding Ramsey numbers of certain graphs, allows us to improve the previously best lower bounds due to Linial-Rabinovich, Erdos-Hajnal and Alon-Sudakov. As an example, we prove that any n-vertex graph G having an independent set of size 3 among every 7 vertices has alpha (G) >= Omega (n(5)/(12)). This confirms a conjecture of Erdos and Hajnal that alpha (G) should be at least n(1/3)+(epsilon) and brings the exponent halfway to the best possible value of 1/2. Our second approach deals with upper bounds. It relies on a reduction of the original question to the following natural extremal problem. What is the minimum possible value of the 2-density (The 2-density of a graph H is defined as m(2)( H) := max(H)'subset of H,|H' |>= 3 (e(H')-1) / (vertical bar H'vertical bar - 2) of a graph on m vertices having no independent set of size r? This allows us to improve previous upper bounds due to Linial-Rabinovich, Krivelevich and Kostochka-Jancey. As part of our arguments, we link the problem of Erdos-Hajnal and Linial- Rabinovich and our new extremal 2-density problem to a number of other well-studied questions. This leads to many interesting directions for future research., Combinatorica, ISSN:0209-9683, ISSN:1439-6912

Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$-regular $n$-vertex graph $G$ whose second largest eigenvalue in absolute value $\lambda(G)$ is at most $\frac{d}{C}$, for some universal constant $C>0$, has a Hamilton cycle. In this paper, we obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree $d$ is at least a small power of $n$. Secondly, in the general case we show that $\lambda(G) \leq \frac{d}{C(\log n)^{1/3}}$ implies the existence of a Hamilton cycle, improving the 20-year old bound of $\frac{d}{ \log^{1-o(1)} n}$ of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust P\'osa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications, giving best bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lov\'asz. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.

The bipartite independence number of a graph $G$, denoted as $\tilde\alpha(G)$, is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a+b=k+1$ with the property that for any two sets $A,B\subseteq V(G)$ with $|A|=a$ and $|B|=b$, there is an edge between $A$ and $B$. McDiarmid and Yolov showed that if $\delta(G)\geq\tilde \alpha(G)$ then $G$ is Hamiltonian, extending the famous theorem of Dirac which states that if $\delta(G)\geq |G|/2$ then $G$ is Hamiltonian. In 1973, Bondy showed that, unless $G$ is a complete bipartite graph, Dirac's Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from $3$ up to $n$. In this paper we show that $\delta(G)\geq\tilde \alpha(G)$ implies that $G$ is pancyclic or that $G=K_{\frac{n}{2},\frac{n}{2}}$, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.

For a positive integer t$t$, let Ft$F_t$ denote the graph of the txt$t\times t$ grid. Motivated by a 50-year-old conjecture of Erdos about Turan numbers of r$r$-degenerate graphs, we prove that there exists a constant C=C(t)$C=C(t)$ such that ex(n,Ft){3/2}$. This bound is tight up to the value of C$C$. One of the interesting ingredients of our proof is a novel way of using the tensor power trick., Bulletin of the London Mathematical Society, 55 (1), ISSN:0024-6093, ISSN:1469-2120

An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $\kappa(G) > (1+o(1)) \alpha(G)$ is pancyclic. This extends the famous Chv\'atal-Erd\H{o}s condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz.

The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph $H$ and $\varepsilon > 0$, if an $n$-vertex graph $G$ contains $\varepsilon n^2$ edge-disjoint copies of $H$ then $G$ contains $\delta n^{v(H)}$ copies of $H$ for some $\delta = \delta(\varepsilon,H) > 0$. The current proofs of the removal lemma give only very weak bounds on $\delta(\varepsilon,H)$, and it is also known that $\delta(\varepsilon,H)$ is not polynomial in $\varepsilon$ unless $H$ is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that $\delta(\varepsilon,H)$ depends polynomially or linearly on $\varepsilon$. In this paper we answer several questions of Fox and Wigderson on this topic.

In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lovász theta function of its complement. We combine this with known bounds on the Lovász theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$., 7 pages

An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $κ(G) > (1+o(1)) α(G)$ is pancyclic. This extends the famous Chvátal-Erdős condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz.

A chordal graph is a graph with no induced cycles of length at least 4. Let f(n, m) be the maximal integer such that every graph with n vertices and m edges has a chordal subgraph with at least f(n, m) edges. In 1985 Erdos and Laskar posed the problem of estimating f (n, m). In the late 1980s, Erdos, Gyarfas, Ordman and Zalcstein determined the value of f (n, n(2)/4 + 1) and made a conjecture on the value off (n, n(2)/3 + 1). In this paper we prove this conjecture and answer the question of Erdos and Laskar, determining f(n, m) asymptotically for all m and exactly for m = n(2)/3 + 1., Combinatorics, Probability & Computing, ISSN:0963-5483, ISSN:1469-2163

How many edges in an $n$-vertex graph will force the existence of a cycle with as many chords as it has vertices? Almost 30 years ago, Chen, Erd\H{o}s and Staton considered this question and showed that any $n$-vertex graph with $2n^{3/2}$ edges contains such a cycle. We significantly improve this old bound by showing that $\Omega(n\log^8n)$ edges are enough to guarantee the existence of such a cycle. Our proof exploits a delicate interplay between certain properties of random walks in almost regular expanders. We argue that while the probability that a random walk of certain length in an almost regular expander is self-avoiding is very small, one can still guarantee that it spans many edges (and that it can be closed into a cycle) with large enough probability to ensure that these two events happen simultaneously., Comment: 12 pages

In 1964, Erd\H{o}s proposed the problem of estimating the Tur\'an number of the $d$-dimensional hypercube $Q_d$. Since $Q_d$ is a bipartite graph with maximum degree $d$, it follows from results of F\"uredi and Alon, Krivelevich, Sudakov that $\mathrm{ex}(n,Q_d)=O_d(n^{2-1/d})$. A recent general result of Sudakov and Tomon implies the slightly stronger bound $\mathrm{ex}(n,Q_d)=o(n^{2-1/d})$. We obtain the first power-improvement for this old problem by showing that $\mathrm{ex}(n,Q_d)=O_d(n^{2-\frac{1}{d-1}+\frac{1}{(d-1)2^{d-1}}})$. This answers a question of Liu. Moreover, our techniques give a power improvement for a larger class of graphs than cubes. We use a similar method to prove that any $n$-vertex, properly edge-coloured graph without a rainbow cycle has at most $O(n(\log n)^2)$ edges, improving the previous best bound of $n(\log n)^{2+o(1)}$ by Tomon. Furthermore, we show that any properly edge-coloured $n$-vertex graph with $\omega(n\log n)$ edges contains a cycle which is almost rainbow: that is, almost all edges in it have a unique colour. This latter result is tight., Comment: 18 pages

Let $\mathcal{F}\subset 2^{[n]}$ be a set family such that the intersection of any two members of $\mathcal{F}$ has size divisible by $\ell$. The famous Eventown theorem states that if $\ell=2$ then $|\mathcal{F}|\leq 2^{\lfloor n/2\rfloor}$, and this bound can be achieved by, e.g., an `atomic' construction, i.e. splitting the ground set into disjoint pairs and taking their arbitrary unions. Similarly, splitting the ground set into disjoint sets of size $\ell$ gives a family with pairwise intersections divisible by $\ell$ and size $2^{\lfloor n/\ell\rfloor}$. Yet, as was shown by Frankl and Odlyzko, these families are far from maximal. For infinitely many $\ell$, they constructed families $\mathcal{F}$ as above of size $2^{Ω(n\log \ell/\ell)}$. On the other hand, if the intersection of any number of sets in $\mathcal{F}\subset 2^{[n]}$ has size divisible by $\ell$, then it is easy to show that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$. In 1983 Frankl and Odlyzko conjectured that $|\mathcal{F}|\leq 2^{(1+o(1)) n/\ell}$ holds already if one only requires that for some $k=k(\ell)$ any $k$ distinct members of $\mathcal{F}$ have an intersection of size divisible by $\ell$. We completely resolve this old conjecture in a strong form, showing that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}+O(1)$ if $k$ is chosen appropriately, and the $O(1)$ error term is not needed if (and only if) $\ell \, | \, n$, and $n$ is sufficiently large. Moreover the only extremal configurations have `atomic' structure as above. Our main tool, which might be of independent interest, is a structure theorem for set systems with small 'doubling'., Discrete Analysis, 11, ISSN:2397-3129

An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices, and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. In 1972, Erd\H{o}s conjectured that every Hamiltonian graph with independence number at most $k$ and at least $n = \Omega(k^2)$ vertices is pancyclic. In this paper we prove this old conjecture in a strong form by showing that if such a graph has $n = (2+o(1))k^2$ vertices, it is already pancyclic, and this bound is asymptotically best possible., Comment: 13 pages, 3 figures

The Ramsey number $r(H)$ of a graph $H$ is the minimum $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. The threshold Ramsey multiplicity $m(H)$ is then the minimum number of monochromatic copies of $H$ taken over all two-edge-colorings of $K_{r(H)}$. The study of this concept was first proposed by Harary and Prins almost fifty years ago. In a companion paper, the authors have shown that there is a positive constant $c$ such that the threshold Ramsey multiplicity for a path or even cycle with $k$ vertices is at least $(ck)^k$, which is tight up to the value of $c$. Here, using different methods, we show that the same result also holds for odd cycles with $k$ vertices., Comment: 17 pages

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also optimal up to the constant hidden in the $O(.)$ notation, and resolves a conjecture of Verstraëte., 11 pages

In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets V1,…,Vn of size k, with exactly one edge between any pair Vi,Vj, how large can n be such that there will always be an independent transversal? They showed that the maximal n is at most (1+o(1))k2, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a 2e-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if n≤(1−o(1))k2, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are ‘locally sparse’, meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global maximum degree condition for the existence of an independent transversal. We show that this can be relaxed to an average degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős–Gyárfás–Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest., Journal of Combinatorial Theory. Series B, 154, ISSN:0095-8956

For a hypergraph H$H$, define its intersection spectrum I(H)$I(H)$ as the set of all intersection sizes |E boolean AND F|$|E\cap F|$ of distinct edges E,F is an element of E(H)$E,F\in E(H)$. In their seminal paper from 1973 which introduced the local lemma, Erdos and Lovasz asked: how large must the intersection spectrum of a k$k$-uniform 3-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with k$k$. Despite the problem being reiterated several times over the years by Erdos and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdos-Lovasz conjecture in a strong form by showing that there are at least k1/2-o(1)$k{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey-type arguments and a density increment approach., Proceedings of the London Mathematical Society, 124 (5), ISSN:0024-6115, ISSN:1460-244X

In this paper we completely resolve the well-known problem of Erd\H{o}s and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log \log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, R\"odl and Szemer\'edi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough. Our method can also be used to settle asymptotically a problem raised by Erd\H{o}s and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree., Comment: 14 pages

For a positive integer $t$, let $F_t$ denote the graph of the $t\times t$ grid. Motivated by a 50-year-old conjecture of Erd\H{o}s about Tur\'{a}n numbers of $r$-degenerate graphs, we prove that there exists a constant $C=C(t)$ such that $\mathrm{ex}(n,F_t)\leq Cn^{3/2}$. This bound is tight up to the value of $C$. One of the interesting ingredients of our proof is a novel way of using the tensor power trick., Comment: 9 pages

For positive integers $s,t,r$, let $K_{s,t}^{(r)}$ denote the $r$-uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X,Y_1,\dots,Y_t$, where $|X| = s$ and $|Y_1| = \dots = |Y_t| = r-1$, and whose edge set is $\{\{x\} \cup Y_i: x \in X, 1\leq i\leq t\}$. The study of the Tur\'an function of $K_{s,t}^{(r)}$ received considerable interest in recent years. Our main results are as follows. First, we show that \begin{equation} \mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}) \end{equation} for all $s,t\geq 2$ and $r\geq 3$, improving the power of $n$ in the previously best bound and resolving a question of Mubayi and Verstra\"ete about the dependence of $\mathrm{ex}(n,K_{2,t}^{(3)})$ on $t$. Second, we show that this upper bound is tight when $r$ is even and $t \gg s$. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for $r = 3$, namely that $\mathrm{ex}(n,K_{s,t}^{(3)}) = O_{s,t}(n^{3 - \frac{1}{s-1} - \varepsilon_s})$ (for all $s\geq 3$). This indicates that the behaviour of $\mathrm{ex}(n,K_{s,t}^{(r)})$ might depend on the parity of $r$. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Tur\'an problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Koll\'ar, R\'onyai and Szab\'o., Comment: 14 pages

In this paper we prove several results on Ramsey numbers $R(H,F)$ for a fixed graph $H$ and a large graph $F$, in particular for $F = K_n$. These results extend earlier work of Erd\H{o}s, Faudree, Rousseau and Schelp and of Balister, Schelp and Simonovits on so-called Ramsey size-linear graphs. Among others, we show that if $H$ is a subdivision of $K_4$ with at least $6$ vertices, then $R(H,F) = O(v(F) + e(F))$ for every graph $F$. We also conjecture that if $H$ is a connected graph with $e(H) - v(H) \leq \binom{k+1}{2} - 2$, then $R(H,K_n) = O(n^k)$. The case $k=2$ was proved by Erd\H{o}s, Faudree, Rousseau and Schelp. We prove the case $k=3$.

For which graphs F is there a sparse F-counting lemma in C₄-free graphs? We are interested in identifying graphs F with the property that, roughly speaking, if G is an n-vertex C₄-free graph with on the order of n³/² edges, then the density of F in G, after a suitable normalization, is approximately at least the density of F in an e-regular approximation of G. In recent work, motivated by applications in extremal and additive combinatorics, we showed that C₅ has this property. Here we construct a family of graphs with the property. ISSN:1558-8599 ISSN:1549-6724 ISSN:1558-8602

For positive integers $s,t,r$, let $K_{s,t}^{(r)}$ denote the $r$-uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X,Y_1,\dots,Y_t$, where $|X| = s$ and $|Y_1| = \dots = |Y_t| = r-1$, and whose edge set is $\{\{x\} \cup Y_i: x \in X, 1\leq i\leq t\}$. The study of the Tur��n function of $K_{s,t}^{(r)}$ received considerable interest in recent years. Our main results are as follows. First, we show that \begin{equation} \mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}) \end{equation} for all $s,t\geq 2$ and $r\geq 3$, improving the power of $n$ in the previously best bound and resolving a question of Mubayi and Verstra��te about the dependence of $\mathrm{ex}(n,K_{2,t}^{(3)})$ on $t$. Second, we show that this upper bound is tight when $r$ is even and $t \gg s$. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for $r = 3$, namely that $\mathrm{ex}(n,K_{s,t}^{(3)}) = O_{s,t}(n^{3 - \frac{1}{s-1} - \varepsilon_s})$ (for all $s\geq 3$). This indicates that the behaviour of $\mathrm{ex}(n,K_{s,t}^{(r)})$ might depend on the parity of $r$. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Tur��n problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Koll��r, R��nyai and Szab��., 14 pages

For a positive integer $t$, let $F_t$ denote the graph of the $t\times t$ grid. Motivated by a 50-year-old conjecture of Erd��s about Tur��n numbers of $r$-degenerate graphs, we prove that there exists a constant $C=C(t)$ such that $\mathrm{ex}(n,F_t)\leq Cn^{3/2}$. This bound is tight up to the value of $C$. One of the interesting ingredients of our proof is a novel way of using the tensor power trick., 9 pages

In 1964, Erdős proposed the problem of estimating the Turán number of the $d$-dimensional hypercube $Q_d$. Since $Q_d$ is a bipartite graph with maximum degree $d$, it follows from results of Füredi and Alon, Krivelevich, Sudakov that $\mathrm{ex}(n,Q_d)=O_d(n^{2-1/d})$. A recent general result of Sudakov and Tomon implies the slightly stronger bound $\mathrm{ex}(n,Q_d)=o(n^{2-1/d})$. We obtain the first power-improvement for this old problem by showing that $\mathrm{ex}(n,Q_d)=O_d(n^{2-\frac{1}{d-1}+\frac{1}{(d-1)2^{d-1}}})$. This answers a question of Liu. Moreover, our techniques give a power improvement for a larger class of graphs than cubes. We use a similar method to prove that any $n$-vertex, properly edge-coloured graph without a rainbow cycle has at most $O(n(\log n)^2)$ edges, improving the previous best bound of $n(\log n)^{2+o(1)}$ by Tomon. Furthermore, we show that any properly edge-coloured $n$-vertex graph with $ω(n\log n)$ edges contains a cycle which is almost rainbow: that is, almost all edges in it have a unique colour. This latter result is tight., 18 pages

One of the central questions in Ramsey theory asks how small can be the size of the largest clique and independent set in a graph on $N$ vertices. By the celebrated result of Erd\H{o}s from 1947, the random graph on $N$ vertices with edge probability $1/2$, contains no clique or independent set larger than $2\log_2 N$, with high probability. Finding explicit constructions of graphs with similar Ramsey-type properties is a famous open problem. A natural approach is to construct such graphs using algebraic tools. Say that an $r$-uniform hypergraph $\mathcal{H}$ is \emph{algebraic of complexity $(n,d,m)$} if the vertices of $\mathcal{H}$ are elements of $\mathbb{F}^{n}$ for some field $\mathbb{F}$, and there exist $m$ polynomials $f_1,\dots,f_m:(\mathbb{F}^{n})^{r}\rightarrow \mathbb{F}$ of degree at most $d$ such that the edges of $\mathcal{H}$ are determined by the zero-patterns of $f_1,\dots,f_m$. The aim of this paper is to show that if an algebraic graph (or hypergraph) of complexity $(n,d,m)$ has good Ramsey properties, then at least one of the parameters $n,d,m$ must be large. In 2001, R\'onyai, Babai and Ganapathy considered the bipartite variant of the Ramsey problem and proved that if $G$ is an algebraic graph of complexity $(n,d,m)$ on $N$ vertices, then either $G$ or its complement contains a complete balanced bipartite graph of size $\Omega_{n,d,m}(N^{1/(n+1)})$. We extend this result by showing that such $G$ contains either a clique or an independent set of size $N^{\Omega(1/ndm)}$ and prove similar results for algebraic hypergraphs of constant complexity. We also obtain a polynomial regularity lemma for $r$-uniform algebraic hypergraphs that are defined by a single polynomial, that might be of independent interest. Our proofs combine algebraic, geometric and combinatorial tools., Comment: 23 pages

We prove that the maximum number of edges in a 3-uniform linear hypergraph on $n$ vertices containing no 2-regular subhypergraph is $n^{1+o(1)}$. This resolves a conjecture of Dellamonica, Haxell, Luczak, Mubayi, Nagle, Person, R\"odl, Schacht and Verstra\"ete. We use this result to show that the maximum number of edges in a $3$-uniform hypergraph on $n$ vertices containing no immersion of a closed surface is $n^{2+o(1)}$. Furthermore, we present results on the maximum number of edges in $k$-uniform linear hypergraphs containing no $r$-regular subhypergraph., Comment: 18 pages

In this paper we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log \log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough. Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree., 14 pages

The Ramsey number $r(H)$ of a graph $H$ is the minimum integer $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. While this definition only asks for a single monochromatic copy of $H$, it is often the case that every two-edge-coloring of the complete graph on $r(H)$ vertices contains many monochromatic copies of $H$. The minimum number of such copies over all two-colorings of $K_{r(H)}$ will be referred to as the threshold Ramsey multiplicity of $H$. Addressing a problem of Harary and Prins, who were the first to systematically study this quantity, we show that there is a positive constant $c$ such that the threshold Ramsey multiplicity of a path or an even cycle on $k$ vertices is at least $(ck)^k$. This bound is tight up to the constant $c$. We prove a similar result for odd cycles in a companion paper., 28 pages

An $n$-queens configuration is a placement of $n$ mutually non-attacking queens on an $n\times n$ chessboard. The $n$-queens completion problem, introduced by Nauck in 1850, is to decide whether a given partial configuration can be completed to an $n$-queens configuration. In this paper, we study an extremal aspect of this question, namely: how small must a partial configuration be so that a completion is always possible? We show that any placement of at most $n/60$ mutually non-attacking queens can be completed. We also provide partial configurations of roughly $n/4$ queens that cannot be completed, and formulate a number of interesting problems. Our proofs connect the queens problem to rainbow matchings in bipartite graphs and use probabilistic arguments together with linear programming duality., to appear in Research in the Mathematical Sciences

A collection of distinct sets is called a sunflower if the intersection of any pair of sets equals the common intersection of all the sets. Sunflowers are fundamental objects in extremal set theory with relations and applications to many other areas of mathematics as well as theoretical computer science. A central problem in the area due to Erd\H{o}s and Rado from 1960 asks for the minimum number of sets of size $r$ needed to guarantee the existence of a sunflower of a given size. Despite a lot of recent attention including a polymath project and some amazing breakthroughs, even the asymptotic answer remains unknown. We study a related problem first posed by Duke and Erd\H{o}s in 1977 which requires that in addition the intersection size of the desired sunflower be fixed. This question is perhaps even more natural from a graph theoretic perspective since it asks for the Tur\'an number of a hypergraph made by the sunflower consisting of $k$ edges, each of size $r$ and with common intersection of size $t$. For a fixed size of the sunflower $k$, the order of magnitude of the answer has been determined by Frankl and F\"{u}redi. In the 1980's, with certain applications in mind, Chung, Erd\H{o}s and Graham and Chung and Erd\H{o}s considered what happens if one allows $k$, the size of the desired sunflower, to grow with the size of the ground set. In the three uniform case $r=3$ the correct dependence on the size of the sunflower has been determined by Duke and Erd\H{o}s and independently by Frankl and in the four uniform case by Buci\'{c}, Dragani\'{c}, Sudakov and Tran. We resolve this problem for any uniformity, by determining up to a constant factor the $n$-vertex Tur\'an number of a sunflower of arbitrary uniformity $r$, common intersection size $t$ and with the size of the sunflower $k$ allowed to grow with $n$.

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares and has been the focus of extensive research ever since. Many conjectures in this area roughly say that 'every edge coloured graph of a certain type contains a rainbow matching using every colour'. In this paper we introduce a versatile 'sampling trick', which allows us to obtain short proofs of old results as well as to solve asymptotically some well known conjectures. - We give a simple proof of Pokrovskiy's asymptotic version of the Aharoni-Berger conjecture with greatly improved error term. - We give the first asymptotic proof of the 'non-bipartite' Aharoni-Berger conjecture, solving two conjectures of Aharoni, Berger, Chudnovsky and Zerbib. - We give a very short asymptotic proof of Grinblat's conjecture (first obtained by Clemens, Ehrenm\"uller, and Pokrovskiy). Furthermore, we obtain a new asymptotically tight bound for Grinblat's problem as a function of edge multiplicity of the corresponding multigraph. - We give the first asymptotic proof of a 30 year old conjecture of Alspach.

The MaxCut problem asks for the size mc(G of a largest cut in a graph G, It is well known that mc(G) >= m/2 for any m-edge graph G, and the difference mc(G) - m/2 is called the surplus of G. The study of the surplus of H-free graphs was initiated by Erdos and Lovasz in the 70s, who, in particular, asked what happens for triangle-free graphs. This was famously resolved by Alon, who showed that in the triangle-free case the surplus is Omega(m(4/5)), and found constructionsmatching this bound. We prove several new results in this area. i) Confirming a conjecture of Alon, Krivelevich and Sudakov, we show that for every fixed odd r >= 3, any C-r-free graph with m edges has surplus Omega(r) (mr+1/r+2). This is tight, as is shown by a construction of pseudo-random C-r-free graphs due to Alon and Kahale. It improves previous results of several researchers, and complements a result of Alon, Krivelevich and Sudakov which is the same bound when r is even. (ii) Generalising the result of Alon, we allow the graph to have triangles, and show that if the number of triangles is a bit less than in a random graph with the same density, then the graph has large surplus. For regular graphs, our bounds on the surplus are sharp. (iii) We prove that a n-vertex graph with few copies of K-r and average degree.. has surplus Omega(r) (d(r-1)/n(r-3) ),which is tight when.. is close to.. provided that a conjectured dense pseudo-random K-r-free graph exists. This result is used to improve the best known lower bound (as a function of m) on the surplus of K-r-free graphs. Our proofs combine techniques from semi-definite programming, probabilistic reasoning, as well as combinatorial and spectral arguments., Journal of the London Mathematical Society, ISSN:0024-6107, ISSN:1469-7750

A basic result in graph theory says that any $n$-vertex tournament with in- and out-degrees larger than $\frac{n-2}{4}$ contains a Hamilton cycle, and this is tight. In 1990, Bollob\'{a}s and H\"{a}ggkvist significantly extended this by showing that for any fixed $k$ and $\varepsilon > 0$, and sufficiently large $n$, all tournaments with degrees at least $\frac{n}{4}+\varepsilon n$ contain the $k$-th power of a Hamilton cycle. Up until now, there has not been any progress on determining a more accurate error term in the degree condition, neither in understanding how large $n$ should be in the Bollob\'{a}s-H\"{a}ggkvist theorem. We essentially resolve both of these questions. First, we show that if the degrees are at least $\frac{n}{4} + cn^{1-1/\lceil k/2 \rceil}$ for some constant $c = c(k)$, then the tournament contains the $k$-th power of a Hamilton cycle. In particular, in order to guarantee the square of a Hamilton cycle, one only requires a constant additive term. We also present a construction which, modulo a well-known conjecture on Tur\'an numbers for complete bipartite graphs, shows that the error term must be of order at least $n^{1-1/\lceil (k-1)/2 \rceil}$, which matches our upper bound for all even $k$. For odd $k$, we believe that the lower bound can be improved. Indeed, we show that for $k=3$, there exist tournaments with degrees $\frac{n}{4}+\Omega(n^{1/5})$ and no cube of a Hamilton cycle. In addition, our results imply that the Bollob\'{a}s-H\"{a}ggkvist theorem already holds for $n = \varepsilon^{-\Theta(k)}$, which is best possible.

A collection of distinct sets is called a sunflower if the intersection of any pair of sets equals the common intersection of all the sets. Sunflowers are fundamental objects in extremal set theory with relations and applications to many other areas of mathematics as well as theoretical computer science. A central problem in the area due to Erd��s and Rado from 1960 asks for the minimum number of sets of size $r$ needed to guarantee the existence of a sunflower of a given size. Despite a lot of recent attention including a polymath project and some amazing breakthroughs, even the asymptotic answer remains unknown. We study a related problem first posed by Duke and Erd��s in 1977 which requires that in addition the intersection size of the desired sunflower be fixed. This question is perhaps even more natural from a graph theoretic perspective since it asks for the Tur��n number of a hypergraph made by the sunflower consisting of $k$ edges, each of size $r$ and with common intersection of size $t$. For a fixed size of the sunflower $k$, the order of magnitude of the answer has been determined by Frankl and F��redi. In the 1980's, with certain applications in mind, Chung, Erd��s and Graham and Chung and Erd��s considered what happens if one allows $k$, the size of the desired sunflower, to grow with the size of the ground set. In the three uniform case $r=3$ the correct dependence on the size of the sunflower has been determined by Duke and Erd��s and independently by Frankl and in the four uniform case by Buci��, Dragani��, Sudakov and Tran. We resolve this problem for any uniformity, by determining up to a constant factor the $n$-vertex Tur��n number of a sunflower of arbitrary uniformity $r$, common intersection size $t$ and with the size of the sunflower $k$ allowed to grow with $n$.

An old conjecture of Bollob\'as and Scott asserts that every Eulerian directed graph with average degree $d$ contains a directed cycle of length at least $\Omega(d)$. The best known lower bound for this problem is $\Omega(d^{1/2})$ by Huang, Ma, Shapira, Sudakov and Yuster. They asked whether this estimate can be improved at least for directed paths instead of cycles and whether one can find a long path starting from any vertex if the host digraph is connected. In this paper we break the $\sqrt{d}$ barrier, showing how to find a path of length $\Omega(d^{1/2+1/40})$ from any vertex of a connected Eulerian digraph., Comment: 14 pages

In this note we show that every tournament on $n$ vertices contains the $k$-th power of a directed path of length $n/2^{6k+7}$, which improves upon the recent bound of Scott and Kor\'{a}ndi of $n/2^{2^{3k}}$. By doing so, we get an inverse exponential dependence on $k$, which is best possible as Yuster recently showed an upper bound of $kn/{2^{k/2}}$., Comment: 2 pages

ISSN:0002-9939 ISSN:1088-6826

A Latin square of order $n$ is an $n \times n$ array filled with $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\times n$ contains a transversal of order $n-1$. In this paper we prove the existence of a transversal of order $n-O(\log{n}/\log{\log{n}})$, improving the celebrated bound of $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$ is guaranteed to have a matching of size $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)}$. Finally, we also show that $O(n\log{n}/\log{\log{n}})$ many symbols in Latin arrays suffice to guarantee a full transversal, improving on previously known bound of $n^{2-\varepsilon}$. The proofs combine in a novel way the semirandom 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}})$ vertices. All previous results, based on the semi-random method, left uncovered at least $\Omega(n^{\alpha})$ (for some constant $\alpha$) vertices.

A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$., Comment: 37 pages, 4 figures

The extremal number of a graph $H$, denoted by $\mbox{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The celebrated K\H{o}v\'ari-S\'os-Tur\'an theorem says that for a complete bipartite graph with parts of size $t\leq s$ the extremal number is $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$. It is also known that this bound is sharp if $s>(t-1)!$. In this paper, we prove that if $H$ is a bipartite graph such that all vertices in one of its parts have degree at most $t$, but $H$ contains no copy of $K_{t,t}$, then $\mbox{ex}(n,H)=o(n^{2-1/t})$. This verifies a conjecture of Conlon, Janzer and Lee., Comment: 8 pages

The conjecture of Brown, Erd\H{o}s and S\'os from 1973 states that, for any $k \ge 3$, if a $3$-uniform hypergraph $H$ with $n$ vertices does not contain a set of $k+3$ vertices spanning at least $k$ edges then it has $o(n^2)$ edges. The case $k=3$ of this conjecture is the celebrated $(6,3)$-theorem of Ruzsa and Szemer\'edi which implies Roth's theorem on $3$-term arithmetic progressions in dense sets of integers. Solymosi observed that, in order to prove the conjecture, one can assume that $H$ consists of triples $(a, b, ab)$ of some finite quasigroup $\Gamma$. Since this problem remains open for all $k \geq 4$, he further proposed to study triple systems coming from finite groups. In this case he proved that the conjecture holds also for $k = 4$. Here we completely resolve the Brown-Erd\H{o}s-S\'os conjecture for all finite groups and values of $k$. Moreover, we prove that the hypergraphs coming from groups contain sets of size $\Theta(\sqrt{k})$ which span $k$ edges. This is best possible and goes far beyond the conjecture.

The extremal number of a graph $H$, denoted by $\mbox{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The celebrated K��v��ri-S��s-Tur��n theorem says that for a complete bipartite graph with parts of size $t\leq s$ the extremal number is $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$. It is also known that this bound is sharp if $s>(t-1)!$. In this paper, we prove that if $H$ is a bipartite graph such that all vertices in one of its parts have degree at most $t$, but $H$ contains no copy of $K_{t,t}$, then $\mbox{ex}(n,H)=o(n^{2-1/t})$. This verifies a conjecture of Conlon, Janzer and Lee., 8 pages

Say that a graph G has property $\mathcal{K}$ if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set $N:= \binom{n}{2}$ and let $e_1, e_2, \dots e_{N}$ be a uniformly random ordering of the edges of $K_n$, with $n$ an even integer. Let $G_0$ be the empty graph on $n$ vertices. For $m \geq 0$, $G_{m+1}$ is obtained from $G_m$ by adding the edge $e_{m+1}$ exactly if $G_m \cup \{ e_{m+1}\}$ has property $\mathcal{K}$. We analyse the behaviour of this process, focusing mainly on two questions: What can be said about the structure of $G_N$ and for which $m$ will $G_m$ contain a perfect matching?

The conjecture of Brown, Erd��s and S��s from 1973 states that, for any $k \ge 3$, if a $3$-uniform hypergraph $H$ with $n$ vertices does not contain a set of $k+3$ vertices spanning at least $k$ edges then it has $o(n^2)$ edges. The case $k=3$ of this conjecture is the celebrated $(6,3)$-theorem of Ruzsa and Szemer��di which implies Roth's theorem on $3$-term arithmetic progressions in dense sets of integers. Solymosi observed that, in order to prove the conjecture, one can assume that $H$ consists of triples $(a, b, ab)$ of some finite quasigroup $��$. Since this problem remains open for all $k \geq 4$, he further proposed to study triple systems coming from finite groups. In this case he proved that the conjecture holds also for $k = 4$. Here we completely resolve the Brown-Erd��s-S��s conjecture for all finite groups and values of $k$. Moreover, we prove that the hypergraphs coming from groups contain sets of size $��(\sqrt{k})$ which span $k$ edges. This is best possible and goes far beyond the conjecture.

We show that there is a positive constant $c$ such that any graph on vertex set $[n]$ with at most $c n^2/k^2 \log k$ edges contains an independent set of order $k$ whose vertices form an arithmetic progression. We also present applications of this result to several questions in Ramsey theory., Comment: 4 pages

Given a graph $G$ and a bijection $f : E(G)\rightarrow \{1, 2, \ldots,e(G)\}$, we say that a trail/path in $G$ is $f$-\emph{increasing} if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chv\'atal and Koml\'os raised the question of providing the worst-case estimates of the length of the longest increasing trail/path over all edge orderings of $K_n$. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is $n-1$, and the case of a path is still widely open. Recently Lavrov and Loh proposed to study the average case of this problem in which the edge ordering is chosen uniformly at random. They conjectured (and it was proved by Martinsson) that such an ordering with high probability (whp) contains an increasing Hamilton path. In this paper we consider random graph $G=G(n,p)$ and its edge ordering chosen uniformly at random. In this setting we determine whp the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average case of the result of Graham and Kleitman, showing that the random edge ordering of $K_n$ has whp an increasing trail of length $(1-o(1))en$ and this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erd\H{o}-Renyi graphs with $p=o(1)$.

The $k$-colour bipartite Ramsey number of a bipartite graph $H$ is the least integer $n$ for which every $k$-edge-coloured complete bipartite graph $K_{n,n}$ contains a monochromatic copy of $H$. The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel, who determined the $2$-colour Ramsey number of paths. In this paper we determine asymptotically the $3$-colour bipartite Ramsey number of paths and (even) cycles., Comment: 15 pages, 3 figures