Search

The canonical Ramsey theorem of Erd\H{o}s and Rado implies that for any graph $H$, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph $K_N$ contains a monochromatic, lexicographic, or rainbow copy of $H$. The least such $N$ is called the Erd\H{o}s-Rado number of $H$, denoted by $ER(H)$. Erd\H{o}s-Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erd\H{o}s-Rado numbers of sparse graphs. For example, we prove that if $H$ has bounded degree, then $ER(H)$ is polynomial in $|V(H)|$ if $H$ is bipartite, but exponential in general. We also study the closely-related problem of constrained Ramsey numbers. For a given tree $S$ and given path $P_t$, we study the minimum $N$ such that every edge-coloring of $K_N$ contains a monochromatic copy of $S$ or a rainbow copy of $P_t$. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse-Ackermann type., Comment: 25 pages

In 1992, Erd\H{o}s and Hajnal posed the following natural problem: Does there exist, for every $r\in \mathbb{N}$, an integer $F(r)$ such that every graph with chromatic number at least $F(r)$ contains $r$ edge-disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist $n$-vertex graphs with fractional chromatic number $\Omega\left(\frac{\log \log n}{\log \log \log n}\right)$ that do not even contain a $4$-regular subgraph. This implies that no such number $F(r)$ exists for $r\ge 2$. We show that assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved.

For two graphs $F,H$ and a positive integer $n$, the function $f_{F,H}(n)$ denotes the largest $m$ such that every $H$-free graph on $n$ vertices contains an $F$-free induced subgraph on $m$ vertices. This function has been extensively studied in the last 60 years when $F$ and $H$ are cliques and became known as the Erd\H{o}s-Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstra\"ete initiated the systematic study of this function in the case where $F$ is a general graph. Answering, in a strong form, a question of Mubayi and Verstra\"ete, we prove that for every positive integer $r$ and every $K_{r-1}$-free graph $F$, there exists some $\varepsilon_F>0$ such that $f_{F,K_r}(n)=O(n^{1/2-\varepsilon_F})$. This result is tight in two ways. Firstly, it is no longer true if $F$ contains $K_{r-1}$ as a subgraph. Secondly, we show that for all $r\geq 4$ and $\varepsilon>0$, there exists a $K_{r-1}$-free graph $F$ for which $f_{F,K_r}(n)=\Omega(n^{1/2-\varepsilon})$. Along the way of proving this, we show in particular that for every graph $F$ with minimum degree $t$, we have $f_{F,K_4}(n)=\Omega(n^{1/2-6/\sqrt{t}})$. This answers (in a strong form) another question of Mubayi and Verstra\"ete. Finally, we prove that there exist absolute constants $0

We study the amount of maximal extractable value (MEV) captured by validators, as a function of searcher competition, in blockchains with competitive block building markets such as Ethereum. We argue that the core is a suitable solution concept in this context that makes robust predictions that are independent of implementation details or specific mechanisms chosen. We characterize how much value validators extract in the core and quantify the surplus share of validators as a function of searcher competition. Searchers can obtain at most the marginal value increase of the winning block relative to the best block that can be built without their bundles. Dually this gives a lower bound on the value extracted by the validator. If arbitrages are easy to find and many searchers find similar bundles, the validator gets paid all value almost surely, while searchers can capture most value if there is little searcher competition per arbitrage. For the case of passive block-proposers we study, moreover, mechanisms that implement core allocations in dominant strategies and find that for submodular value, there is a unique dominant-strategy incentive compatible core-selecting mechanism that gives each searcher exactly their marginal value contribution to the winning block. We validate our theoretical prediction empirically with aggregate bundle data and find a significant positive relation between the number of submitted backruns for the same opportunity and the median value captured by the proposer from the opportunity.

A graph $G$ is said to be $p$-locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$. A famous conjecture of Kohayakawa, Nagle, R\"odl, and Schacht predicts that locally dense graphs have, asymptotically, at least as many copies of any fixed graph $H$ as are found in a random graph of edge density $p$. In this paper, we prove several results around the KNRS conjecture. First, we prove that certain natural gluing operations on $H$ preserve this property, thus proving the conjecture for many graphs $H$ for which it was previously unknown. Secondly, we study a stability version of this conjecture, and prove that for many graphs $H$, approximate equality is attained in the KNRS conjecture if and only if the host graph $G$ is quasirandom. Finally, we introduce a weakening of the KNRS conjecture, which requires the host graph to be nearly degree-regular, and prove this conjecture for a larger family of graphs. Our techniques reveal a surprising connection between these questions, semidefinite optimization, and the study of copositive matrices., Comment: 20 pages plus appendix

The celebrated Erd\H{o}s-Hajnal conjecture says that any graph without a fixed induced subgraph $H$ contains a very large homogeneous set. A direct analog of this conjecture is not true for hypergraphs. In this paper we present two natural variants of this problem which do hold for hypergraphs. We show that for every $r \geq 3$, $m \geq m_0(r)$ and $0 \leq f \leq \binom{m}{r}$, if an $r$-graph $G$ does not contain $m$ vertices spanning exactly $f$ edges, then $G$ contains much bigger homogeneous sets than what is guaranteed to exist in general $r$-graphs. We also prove that if a $3$-graph $G$ does not contain homogeneous sets of polynomial size, then for every $m \geq 3$ there are $\Omega(m^3)$ values of $f$ such that $G$ contains $m$ vertices spanning exactly $f$ edges. This makes progress on a conjecture of Axenovich, Brada\v{c}, Gishboliner, Mubayi and Weber.

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

The induced $q$-color size-Ramsey number $\hat{r}_{\text{ind}}(H;q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$-edge-coloring of $G$ contains a monochromatic copy of $H$ which is an induced subgraph of $G$. A natural question, which in the non-induced case has a very long history, asks which families of graphs $H$ have induced Ramsey numbers that are linear in $|H|$. We prove that for every $k,w,q$, if $H$ is an $n$-vertex graph with maximum degree $k$ and treewidth at most $w$, then $\hat{r}_{\text{ind}}(H;q) = O_{k,w,q}(n)$. This extends several old and recent results in Ramsey theory. Our proof is quite simple and relies upon a novel reduction argument., Comment: 17 pages, comments welcome!

We prove the following variant of Helly's classical theorem for Hamming balls with a bounded radius. For $n>t$ and any (finite or infinite) set $X$, if in a family of Hamming balls of radius $t$ in $X^n$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of the family. This is tight for all $|X|>1$ and all $n>t$. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory.

Let $K^r_n$ be the complete $r$-uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n]:=\{1,2,...,n\}$ and whose edge set is $\binom{[n]}{r}$. We form $G^r(n,p)$ by retaining each edge of $K^r_n$ independently with probability $p$. An $r$-uniform hypergraph $H\subseteq G$ is $F$-saturated if $H$ does not contain any copy of $F$, but any missing edge of $H$ in $G$ creates a copy of $F$. Furthermore, we say that $H$ is weakly $F$-saturated in $G$ if $H$ does not contain any copy of $F$, but the missing edges of $H$ in $G$ can be added back one-by-one, in some order, such that every edge creates a new copy of $F$. The smallest number of edges in an $F$-saturated hypergraph in $G$ is denoted by $sat(G,F)$, and in a weakly $F$-saturated hypergraph in $G$ by $wsat(G,F)$. In 2017, Kor\'andi and Sudakov initiated the study of saturation in random graphs, showing that for constant $p$, with high probability $sat(G(n,p),K_s)=(1+o(1))n\log_{\frac{1}{1-p}}n$, and $wsat(G(n,p),K_s)=wsat(K_n,K_s)$. Generalising their results, in this paper, we solve the suturation problem for random hypergraphs for every $2\le r < s$ and constant $p$.

In this paper we study the number of incidences between $m$ points and $n$ varieties in $\mathbb{F}^d$, where $\mathbb{F}$ is an arbitrary field, assuming the incidence graph contains no copy of $K_{s,s}$. We also consider the analogous problem for algebraically defined graphs and unit distance graphs. First, we prove that if $\mathcal{P}$ is a set of $m$ points and $\mathcal{V}$ is a set of $n$ varieties in $\mathbb{F}^{D}$, each of dimension $d$ and degree at most $\Delta$, and in addition the incidence graph is $K_{s,s}$-free, then the number of incidences satisfies $I(\mathcal{P}, \mathcal{V})\leq O_{d,\Delta, s}(m^{\frac{d}{d+1}} n+m)$. This bound is tight when $s,\Delta$ are sufficiently large with respect to $d$, with an appropriate choice of $\mathbb{F}=\mathbb{F}(m,n)$. We give two proofs of this upper bound, one based on the framework of the induced Tur\'an problems and the other based on VC-dimension theory. In the second proof, we extend the celebrated result of R\'onyai, Babai and Ganapathy on the number of zero-patterns of polynomials to the context of varieties, which might be of independent interest. We also resolve the problem of finding the maximum number of unit distances which can be spanned by a set of $n$ points $\mathcal{P}$ in $\mathbb{F^d}$ whose unit-distance graph is $K_{s, s}$-free, showing that it is $\Theta_{d,s}(n^{2-\frac{1}{\lceil d/2\rceil +1}})$. Finally, we obtain tight bounds on the maximum number of edges of a $K_{s, s}$-free algebraic graph defined over a finite field, thus resolving the Zarankiewicz problem for this class of graphs., Comment: This paper is a follow-up to a previous paper arXiv:2401.06670

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications, including to the Hamiltonicity of random Cayley graphs.

Given a $k$-uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $2$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $k$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial (2002), in 2008, Feige conjectured an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $k$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges (Guruswami, Kothari, and 1Manohar 2022 and Hsieh, Kothari, and Mohanty 2023). These works introduce the new technique that relates hypergraph even covers to cycles in the associated \emph{Kikuchi} graphs. Their analysis of these Kikuchi graphs, especially for odd $k$, is rather involved and relies on matrix concentration inequalities. In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige's conjecture for even $k$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $k$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds (Alrabiah, Guruswami, Kothari and Manohar, 2023) on 3-query binary linear locally decodable codes., Comment: 19 pages

The celebrated K\H{o}v\'ari-S\'os-Tur\'an theorem states that any $n$-vertex graph containing no copy of the complete bipartite graph $K_{s,s}$ has at most $O_s(n^{2-1/s})$ edges. In the past two decades, motivated by the applications in discrete geometry and structural graph theory, a number of results demonstrated that this bound can be greatly improved if the graph satisfies certain structural restrictions. We propose the systematic study of this phenomenon, and state the conjecture that if $H$ is a bipartite graph, then an induced $H$-free and $K_{s,s}$-free graph cannot have much more edges than an $H$-free graph. We provide evidence for this conjecture by considering trees, cycles, the cube graph, and bipartite graphs with degrees bounded by $k$ on one side, obtaining in all the cases similar bounds as in the non-induced setting. Our results also have applications to the Erd\H{o}s-Hajnal conjecture, the problem of finding induced $C_4$-free subgraphs with large degree and bounding the average degree of $K_{s, s}$-free graphs which do not contain induced subdivisions of a fixed graph., Comment: 22 pages, including references

The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard non-degeneracy condition, i.e., that no $s$ points are contained in the intersection of $s$ hyperplanes, the currently best known upper bound on the number of incidences of $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ is $$O_{d, s}((mn)^{1-1/(d+1)}+m+n).$$ This bound by Apfelbaum and Sharir is based on geometrical space partitioning techniques, which apply only over the real numbers. In this paper, we propose a novel combinatorial approach to study such incidence problems over arbitrary fields. Perhaps surprisingly, this approach matches the best known bounds for point-hyperplane incidences in $\mathbb{R}^d$ for many interesting values of $m, n, d$, e.g. when $m=n$ and $d$ is odd. Moreover, in finite fields our bounds are sharp as a function of $m$ and $n$ in every dimension. We also study the size of the largest complete bipartite graph in point-hyperplane incidence graphs with a given number of edges and obtain optimal bounds as well. Additionally, we study point-variety incidences and unit-distance problem in finite fields, and give tight bounds for both problems under a similar non-degeneracy assumption. We also resolve Zarankiewicz type problems for algebraic graphs. Our proofs use tools such as induced Tur\'an problems, VC-dimension theory, evasive sets and Hilbert polynomials. Also, we extend the celebrated result of R\'onyai, Babai and Ganapathy on the number of zero-patterns of polynomials to the context of varieties, which might be of independent interest., Comment: The second version of this paper is a combination of its first version with the subsequent paper arXiv:2403.08756, by the same authors on the same topic. Since the merged version will ultimately be submitted for publication, we update the arXiv version to reflect this

The $q$-color Ramsey number of a $k$-uniform hypergraph $G,$ denoted $r(G;q)$, is the minimum integer $N$ such that any coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $G$. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behaviour of $r(G;q)$ for fixed $G$ and $q$ tending to infinity. In this paper we study this problem for $3$-uniform hypergraphs and determine the tower height of $r(G;q)$ as a function of $q$. More precisely, given a hypergraph $G$, we determine when $r(G; q)$ behaves polynomially, exponentially or double-exponentially in $q$. This answers a question of Axenovich, Gy\'{a}rf\'{a}s, Liu and Mubayi.

Many well-studied problems in extremal combinatorics deal with the maximum possible size of a family of objects in which every pair of objects satisfies a given restriction. One problem of this type was recently raised by Alon, Gujgiczer, K\"orner, Milojevi\'c and Simonyi. They asked to determine the maximum size of a family $\mathcal{G}$ of graphs on $[n]$, such that for every two $G_1,G_2 \in \mathcal{G}$, the graphs $G_1 \setminus G_2$ and $G_2 \setminus G_1$ are isomorphic. We completely resolve this problem by showing that this maximum is exactly $2^{\frac{1}{2}\big(\binom{n}{2} - \lfloor \frac{n}{2}\rfloor\big)}$ and characterizing all the extremal constructions. We also prove an analogous result for $r$-uniform hypergraphs.

Let $f(n, v, e)$ denote the maximum number of edges in a 3-uniform hypergraph on $n$ vertices which does not contain $v$ vertices spanning at least $e$ edges. A central problem in extremal combinatorics, famously posed by Brown, Erd\H{o}s and S\'os in 1973, asks whether $f(n, e+3, e)=o(n^2)$ for every $e \ge 3$. A classical result of S\'ark\"ozy and Selkow states that $f(n, e+\lfloor \log_2 e\rfloor+2, e)=o(n^{2})$ for every $e \ge 3$. This bound was recently improved by Conlon, Gishboliner, Levanzov and Shapira. Motivated by applications to other problems, Gowers and Long made the striking conjecture that $f(n, e+4, e)=O(n^{2-\varepsilon})$ for some $\varepsilon=\varepsilon(e)>0$. Conlon, Gishboliner, Levanzov and Shapira, and later, Shapira and Tyomkyn reiterated the following approximate version of this problem. What is the smallest $d(e)$ for which $f(n, e+d(e), e)=O(n^{2-\varepsilon})$ for some $\varepsilon=\varepsilon(e)>0$? In this paper, we prove that for each $e\geq 3$ we have $f(n, e+\lfloor \log_2 e\rfloor +38, e)=O(n^{2-\varepsilon})$ for some $\varepsilon>0$. This shows that one can already obtain power saving near the S\'ark\"ozy-Selkow bound at the cost of a small additive constant., Comment: 12 pages

The goal of this expository note is to give a short, self-contained proof of nearly optimal lower bounds for the second largest eigenvalue of the adjacency matrix of regular graphs., Comment: This is a companion note to arXiv:2311.02070, and we do not plan to publish it as a separate paper

The positive discrepancy of a graph $G$ of edge density $p=e(G)/\binom{v(G)}{2}$ is defined as $$\mbox{disc}^{+}(G)=\max_{U\subset V(G)}e(G[U])-p\binom{|U|}{2}.$$ In 1993, Alon proved (using the equivalent terminology of minimum bisections) that if $G$ is $d$-regular on $n$ vertices, and $d=O(n^{1/9})$, then $\mbox{disc}^{+}(G)=\Omega(d^{1/2}n)$. We greatly extend this by showing that if $G$ has average degree $d$, then $\mbox{disc}^{+}(G)=\Omega(d^{\frac{1}{2}}n)$ if $d\in [0,n^{\frac{2}{3}}]$, $\Omega(n^2/d)$ if $d\in [n^{\frac{2}{3}},n^{\frac{4}{5}}]$, and $\Omega(d^{\frac{1}{4}}n/\log n)$ if $d\in \left[n^{\frac{4}{5}},(\frac{1}{2}-\varepsilon)n\right]$. These bounds are best possible if $d\ll n^{3/4}$, and the complete bipartite graph shows that $\mbox{disc}^{+}(G)=\Omega(n)$ cannot be improved if $d\approx n/2$. Our proofs are based on semidefinite programming and linear algebraic techniques. An interesting corollary of our results is that every $d$-regular graph on $n$ vertices with ${\frac{1}{2}+\varepsilon\leq \frac{d}{n}\leq 1-\varepsilon}$ has a cut of size $\frac{nd}{4}+\Omega(n^{5/4}/\log n)$. This is not necessarily true without the assumption of regularity, or the bounds on $d$. The positive discrepancy of regular graphs is controlled by the second eigenvalue $\lambda_2$, as $\mbox{disc}^{+}(G)\leq \frac{\lambda_2}{2} n+d$. As a byproduct of our arguments, we present lower bounds on $\lambda_2$ for regular graphs, extending the celebrated Alon-Boppana theorem in the dense regime., Comment: 29 pages

In his seminal 1976 paper, P\'osa showed that for all $p\geq C\log n/n$, the binomial random graph $G(n,p)$ is with high probability Hamiltonian. This leads to the following natural questions, which have been extensively studied: How well is it typically possible to cover all edges of $G(n,p)$ with Hamilton cycles? How many cycles are necessary? In this paper we show that for $ p\geq C\log n/n$, we can cover $G\sim G(n,p)$ with precisely $\lceil\Delta(G)/2\rceil$ Hamilton cycles. Our result is clearly best possible both in terms of the number of required cycles, and the asymptotics of the edge probability $p$, since it starts working at the weak threshold needed for Hamiltonicity. This resolves a problem of Glebov, Krivelevich and Szab\'o, and improves upon previous work of Hefetz, K\"uhn, Lapinskas and Osthus, and of Ferber, Kronenberg and Long, essentially closing a long line of research on Hamiltonian packing and covering problems in random graphs., Comment: 13 pages

In 1975, Erd\H{o}s asked the following natural question: What is the maximum number of edges that an $n$-vertex graph can have without containing a cycle with all diagonals? Erd\H{o}s observed that the upper bound $O(n^{5/3})$ holds since the complete bipartite graph $K_{3,3}$ can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this old problem. We prove that there exists a constant $C$ such that every $n$-vertex with $Cn^{3/2}$ edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without a four-cycle based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an `almost-spanning' robust expander which might be of independent interest., Comment: 14 pages, comments welcome!

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 \ge 3$ much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruci\'nski 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., Comment: 35 pages

A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_1, \ldots, H_m$ are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartrand, Erd\H{o}s, and Oellerman. They conjectured that the edges of every graph with $\binom{m+1}2$ edges can be decomposed into subgraphs $H_1, \dots, H_m$ such that each $H_i$ has $i$ edges and is isomorphic to a subgraph of $H_{i+1}$. In this paper we prove this conjecture for sufficiently large $m$.

The $q$-color Ramsey number of a $k$-uniform hypergraph $H$ is the minimum integer $N$ such that any $q$-coloring of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $H$. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erd\H{o}s and Graham asked to maximize the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed $k \ge 3$ and $q \ge 2$ we prove that the largest possible $q$-color Ramsey number of a $k$-uniform hypergraph with $m$ edges is at most $\mathrm{tw}_k(O(\sqrt{m})),$ where $\mathrm{tw}$ denotes the tower function. We also present a construction showing that this bound is tight for $q \ge 4$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for $k \geq 4$ and the lower bound for $k=3$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs.

The study of ordered Ramsey numbers of monotone paths for graphs and hypergraphs has a long history, going back to the celebrated work by Erd\H{o}s and Szekeres in the early days of Ramsey theory. In this paper we obtain several results in this area, establishing two conjectures of Mubayi and Suk and improving bounds due to Balko, Cibulka, Kr\'al and Kyn\v{c}l. We also obtain a color-monotone version of the well-known Canonical Ramsey Theorem of Erd\H{o}s and Rado, which could be of independent interest.

For $2\leq s

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 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: 8 pages

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.

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.

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 induced size-Ramsey number $\hat{r}_\text{ind}^k(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$-coloring of its edges, there exists a monochromatic copy of $H$ which is an induced subgraph of $G$. In 1995, in their seminal paper, Haxell, Kohayakawa and Luczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $\hat{r}_\text{ind}^k(C_n)\leq Cn$ for some $C=C(k)$. The constant $C$ comes from the use of the regularity lemma, and has a tower type dependence on $k$. In this paper we significantly improve these bounds, showing that $\hat{r}_\text{ind}^k(C_n)\leq O(k^{102})n$ when $n$ is even, thus obtaining only a polynomial dependence of $C$ on $k$. We also prove $\hat{r}_\text{ind}^k(C_n)\leq e^{O(k\log k)}n$ for odd $n$, which almost matches the lower bound of $e^{\Omega(k)}n$. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $\hat{r}^k(C_n)=e^{O(k)}n$ for odd $n$. This substantially improves the best previous result of $e^{O(k^2)}n$, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.

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: 19 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$. 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

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

Given positive integers $k\leq d$ and a finite field $\mathbb{F}$, a set $S\subset\mathbb{F}^{d}$ is $(k,c)$-subspace evasive if every $k$-dimensional affine subspace contains at most $c$ elements of $S$. By a simple averaging argument, the maximum size of a $(k,c)$-subspace evasive set is at most $c |\mathbb{F}|^{d-k}$. When $k$ and $d$ are fixed, and $c$ is sufficiently large, the matching lower bound $\Omega(|\mathbb{F}|^{d-k})$ is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of $(k,c)$-evasive sets in case $d$ is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of $k$-dimensional linear hyperplanes needed to cover the grid $[n]^{d}\subset \mathbb{R}^{d}$ is $\Omega_{d}\big(n^{\frac{d(d-k)}{d-1}}\big)$, which matches the upper bound proved by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in $\mathbb{R}^{d}$ assuming their incidence graph avoids the complete bipartite graph $K_{c,c}$ for some large constant $c=c(d)$., Comment: 13 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\"ete., Comment: 11 pages

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 Erd\H{o}s and Laskar posed the problem of estimating $f(n,m)$. In the late '80s, Erd\H{o}s, Gy\'arf\'as, Ordman and Zalcstein determined the value of $f(n,n^2/4+1)$ and made a conjecture on the value of $f(n,n^2/3+1)$. In this paper we prove this conjecture and answer the question of Erd\H{o}s and Laskar, determining $f(n,m)$ asymptotically for all $m$ and exactly for $m \leq n^2/3+1$.

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 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

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