Search

In 1975, Erd\H{o}s asked for the maximum number of edges that an $n$-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Tur\'an-type results can be used to prove an upper bound of $n^{3/2+o(1)}$. However, this approach cannot give an upper bound better than $\Omega(n^{3/2})$. We show that, for any $k\geq 2$, every $n$-vertex graph with at least $n \cdot \mathrm{polylog}(n)$ edges contains $k$ pairwise edge-disjoint cycles with the same vertex set, resolving this old problem in a strong form up to a polylogarithmic factor. The well-known construction of Pyber, R\"odl and Szemer\'edi of graphs without $4$-regular subgraphs shows that there are $n$-vertex graphs with $\Omega(n\log \log n)$ edges which do not contain two cycles with the same vertex set, so the polylogarithmic term in our result cannot be completely removed. Our proof combines a variety of techniques including sublinear expanders, absorption and a novel tool for regularisation, which is of independent interest. Among other applications, this tool can be used to regularise an expander while still preserving certain key expansion properties., Comment: 34 pages, 2 figures

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some $1$-entries with $0$-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted $\operatorname{ex}(n,A)$, is the maximum number of $1$-entries that an $n\times n$ zero-one matrix can have without containing $A$. The systematic study of this function for various patterns $A$ goes back to the work of F\"uredi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (that is, the case where $A$ is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if $A$ has at most $t$ $1$-entries in every row, then $\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$. This verifies a conjecture of Methuku and Tomon. Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number $2$, generalizing a celebrated result of F\"uredi, and Alon, Krivelevich and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree $t$ in one of the vertex classes., Comment: 10 pages

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

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!

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

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and R\"{o}dl conjectured that for any given $\mu>0$, there exists $n_0$ such that the following holds. Every $n$-vertex Steiner triple system contains all hypertrees with at most $(1-\mu)n$ vertices whenever $n\geq n_0$. We prove this conjecture., Comment: 19 pages, 2 figures

We prove that for $n \in \mathbb N$ and an absolute constant $C$, if $p \geq C\log^2 n / n$ and $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k\in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i, j\in [n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$. The problem of determining the threshold probability for the existence of an order-$n$ Latin square was raised independently by Johansson, by Luria and Simkin, and by Casselgren and H{\"a}ggkvist; our result provides an upper bound which is tight up to a factor of $\log n$ and strengthens the bound recently obtained by Sah, Sawhney, and Simkin. We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a $1$-factorization of a nearly complete regular bipartite graph., Comment: 32 pages, 1 figure. Final version, to appear in Transactions of the AMS

In 1977, Erd\H{o}s asked the following question: for any integers $t,n \in \mathbb{N}$, if $G_1 , \dots , G_n$ are complete graphs such that each $G_i$ has at most $n$ vertices and every pair of them shares at most $t$ vertices, what is the largest possible chromatic number of the union $\bigcup_{i=1}^{n} G_i$? The equivalent dual formulation of this question asks for the largest chromatic index of an $n$-vertex hypergraph with maximum degree at most $n$ and codegree at most $t$. For the case $t = 1$, Erd\H{o}s, Faber, and Lov\'{a}sz famously conjectured that the answer is $n$, which was recently proved by the authors for all sufficiently large $n$. In this paper, we answer this question of Erd\H{o}s for $t \geq 2$ in a strong sense, by proving that every $n$-vertex hypergraph with maximum degree at most $(1-o(1))tn$ and codegree at most $t$ has chromatic index at most $tn$ for any $t,n \in \mathbb{N}$. Moreover, equality holds if and only if the hypergraph is a $t$-fold projective plane of order $k$, where $n = k^2 + k + 1$. Thus, for every $t \in \mathbb N$, this bound is best possible for infinitely many integers $n$. This result also holds for the list chromatic index., Comment: 23 pages

The problem of maximising the number of cliques among $n$-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of $1$-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems., Comment: 38 pages, 8 figures

We show that for every integer $m \ge 2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n (\log n)^{53}$ edges contains a rainbow subdivision of $K_m$. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs., Comment: 22 pages, journal version

We show that for any integer $t\geq 2$, every properly edge-coloured graph on $n$ vertices with more than $n^{1+o(1)}$ edges contains a rainbow subdivision of $K_t$. Note that this bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Tur\'an numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting., Comment: 8 pages, journal version

This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble' methods. We also give a detailed sketch of some aspects of the recent proof of the Erd\H{o}s-Faber-Lov\'{a}sz conjecture., Comment: Final version, to appear in the proceedings of the 8th European Congress of Mathematics; 33 pages, 3 figures

The poset Ramsey number $R(Q_m,Q_n)$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_N$ has a blue induced copy of $Q_m$ or a red induced copy of $Q_n$. The weak poset Ramsey number $R_w(Q_m,Q_n)$ is defined analogously, with weak copies instead of induced copies. It is easy to see that $R(Q_m,Q_n) \ge R_w(Q_m,Q_n)$. Axenovich and Walzer showed that $n+2 \le R(Q_2,Q_n) \le 2n+2$. Recently, Lu and Thompson improved the upper bound to $\frac{5}{3}n+2$. In this paper, we solve this problem asymptotically by showing that $R(Q_2,Q_n)=n+O(n/\log n)$. In the diagonal case, Cox and Stolee proved $R_w(Q_n,Q_n) \ge 2n+1$ using a probabilistic construction. In the induced case, Bohman and Peng showed $R(Q_n,Q_n) \ge 2n+1$ using an explicit construction. Improving these results, we show that $R_w(Q_m,Q_n) \ge n+m+1$ for all $m \ge 2$ and large $n$ by giving an explicit construction; in particular, we prove that $R_w(Q_2,Q_n)=n+3$.

The Erd\H{o}s-Faber-Lov\'{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stability versions of this result, which confirm a prediction of Kahn., Comment: 47 pages, 3 figures. Final version, to appear in the Annals of Mathematics

A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s \geq 3$ and $t \geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $\Theta ( n^{t/2})$. More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s \geq 4$ and $t \geq 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $\Omega( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.

Let $H$ be a $k$-uniform $D$-regular simple hypergraph on $N$ vertices. Based on an analysis of the R\"odl nibble, Alon, Kim and Spencer (1997) proved that if $k \ge 3$, then $H$ contains a matching covering all but at most $ND^{-1/(k-1)+o(1)}$ vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all $k > 3$, $H$ contains a matching covering all but at most $ND^{-1/(k-1)-\eta}$ vertices for some $\eta = \Theta(k^{-3}) > 0$, when $N$ and $D$ are sufficiently large. Our approach consists of showing that the R\"odl nibble process not only constructs a large matching but it also produces many well-distributed `augmenting stars' which can then be used to significantly improve the matching constructed by the R\"odl nibble process. Based on this, we also improve the results of Kostochka and R\"odl (1998) and Vu (2000) on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed (2000) on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs)., Comment: 35 pages, 1 figure

In this note we show that the maximum number of edges in a $3$-uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))\frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Gy\H{o}ri and Lemons and by F\"uredi and \"Ozkahya.

The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the vertices and edges of $F$ with independent sets of size $r$ and copies of $K_{r,r}$, respectively. For bipartite graphs $F$, very little is known about the order of magnitude of the Tur\'an number of $F[r]$. In this paper we prove that $\mathrm{ex}(n,C_6[2])=O(n^{5/3})$ and, more generally, for any positive integer $t$, $\mathrm{ex}(n,\theta_{3,t}[2])=O(n^{5/3})$. This is tight when $t$ is sufficiently large., Comment: 14 pages; improved presentation

A hypergraph is linear if any two of its edges intersect in at most one vertex. The Sail (or $3$-fan) $F^3$ is the $3$-uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting all $f_i$ in a vertex different from $v$. The linear Tur\'an number $ex_{lin}(n, F^3)$ is the maximum number of edges in a $3$-uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$. F\"{u}redi and Gy\'arf\'as proved that if $n = 3k$, then $ex_{lin}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$, then $ex_{lin}(n, F^3) = k^2+k$, and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $ex_{lin}(n, F^3) = k^2+1$ if $n = 3k+1$, answering a question of F\"{u}redi and Gy\'arf\'as. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases., Comment: A few minor corrections are made

In this paper we initiate a systematic study of the Tur\'an problem for edge-ordered graphs. A simple graph is called $\textit{edge-ordered}$, if its edges are linearly ordered. An isomorphism between edge-ordered graphs must respect the edge-order. A subgraph of an edge-ordered graph is itself an edge-ordered graph with the induced edge-order. We say that an edge-ordered graph $G$ $\textit{avoids}$ another edge-ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The $\textit{Tur\'an number}$ of an edge-ordered graph $H$ is the maximum number of edges in an edge-ordered graph on $n$ vertices that avoids $H$. We study this problem in general, and establish an Erd\H{o}s-Stone-Simonovits-type theorem for edge-ordered graphs -- we discover that the relevant parameter for the Tur\'an number of an edge-ordered graph is its $\textit{order chromatic number}$. We establish several important properties of this parameter. We also study Tur\'an numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in Discrete Geometry., Comment: 41 pages. Updated grants

Alon and Shikhelman initiated the systematic study of the following generalized Tur\'an problem: for fixed graphs $H$ and $F$ and an integer $n$, what is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Tur\'an number of $F$ is defined as the maximum number of edges in a properly edge-colored graph on $n$ vertices with no rainbow copy of $F$. The study of rainbow Tur\'an problems was initiated by Keevash, Mubayi, Sudakov and Verstra\"ete. Motivated by the above problems, we study the following problem: What is the maximum number of copies of $F$ in a properly edge-colored graph on $n$ vertices without a rainbow copy of $F$? We establish several results, including when $F$ is a path, cycle or tree., Comment: 19 pages

We are given a set $A$ of buyers, a set $B$ of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping $\tau$ from $A$ to $B$, and $\tau$ is strictly better than another house allocation $\tau'\neq \tau$ if for every buyer $i$, $\tau'(i)$ does not come before $\tau(i)$ in the preference list of $i$. A house allocation is Pareto optimal if there is no strictly better house allocation. Let $s(\tau)$ be the image of $\tau$ (i.e., the set of houses sold in the house allocation $\tau$). We are interested in the largest possible cardinality $f(m)$ of the family of sets $s(\tau)$ for Pareto optimal mappings $\tau$ taken over all sets of preference lists of $m$ buyers. We improve the earlier upper bound on $f(m)$ given by Asinowski, Keszegh and Miltzow by making a connection between this problem and some problems in extremal set theory.

A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete some rows and columns of $M$, and turn some 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$. A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $ex(n,A)

Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$. It was shown by Saks and Werman that $m(K_n)=n-b(n)$, where $b(n)$ is the number of 1's in the binary representation of $n$. In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)\le m(G)\le n-1$. We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$ and that for any tree $T$ on an odd number of vertices, we have $n-65\le m(T)\le n-2$. Our proof uses results about the weighted version of the problem for $K_n$, which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices., Comment: 19 pages

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on $n$ vertices may admit. Our results rely on an improved application of an entropy inequality of Shearer., Comment: 14 pages

Let $t$ be an integer such that $t\geq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a,x_i,y_i\}$, $\{b,x_i,y_i\}$ for $1 \le i \le t$, where the elements $a, b, x_1, x_2, \ldots, x_t,$ $y_1, y_2, \ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstra\"ete, where the special case $t=2$ was a problem of Erd\H{o}s that was studied by various authors. Mubayi and Verstra\"ete proved that $ex(n,K_{2,t}^{(3)})

In this paper we show that the maximum number of hyperedges in a $3$-uniform hypergraph on $n$ vertices without a (Berge) cycle of length five is less than $(0.254 + o(1))n^{3/2}$, improving an estimate of Bollob\'as and Gy\H{o}ri. We obtain this result by showing that not many $3$-paths can start from certain subgraphs of the shadow.

For a graph $F$, we say a hypergraph is a Berge-$F$ if it can be obtained from $F$ by replacing each edge of $F$ with a hyperedge containing it. A hypergraph is Berge-$F$-free if it does not contain a subhypergraph that is a Berge-$F$. The weight of a non-uniform hypergraph $\mathcal{H}$ is the quantity $\sum_{h \in E(\mathcal{H})} |h|$. Suppose $\mathcal{H}$ is a Berge-$F$-free hypergraph on $n$ vertices. In this short note, we prove that as long as every edge of $\mathcal{H}$ has size at least the Ramsey number of $F$ and at most $o(n)$, the weight of $\mathcal{H}$ is $o(n^2)$. This result is best possible in some sense. Along the way, we study other weight functions, and strengthen results of Gerbner and Palmer; and Gr\'osz, Methuku and Tompkins., Comment: 7 pages. Results are slightly strengthened, and proofs are made simpler

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$(1 + o(1)) \frac{1}{3 \sqrt 2} n^{3/2}.$$ We also show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size., Comment: 14 pages

A graph is $F$-saturated if it is $F$-free but the addition of any edge creates a copy of $F$. In this paper we study the quantity $\mathrm{sat}(n, H, F)$ which denotes the minimum number of copies of $H$ that an $F$-saturated graph on $n$ vertices may contain. This parameter is a natural saturation analogue of Alon and Shikhelman's generalized Tur\'an problem, and letting $H = K_2$ recovers the well-studied saturation function. We provide a first investigation into this general function focusing on the cases where the host graph is either $K_s$ or $C_k$-saturated. Some representative interesting behavior is: (a) For any natural number $m$, there are graphs $H$ and $F$ such that $\mathrm{sat}(n, H, F) = \Theta(n^m)$. (b) For many pairs $k$ and $l$, we show $\mathrm{sat}(n, C_l, C_k) = 0$. In particular, we prove that there exists a triangle-free $C_k$-saturated graph on $n$ vertices for any $k > 4$ and large enough $n$. (c) $\mathrm{sat}(n, K_3, K_4) = n-2$, $\mathrm{sat}(n, C_4, K_4) \sim \frac{n^2}{2}$, and $\mathrm{sat}(n, C_6, K_5) \sim n^3$. We discuss several intriguing problems which remain unsolved., Comment: 28 pages

We address the following rainbow Ramsey problem: For posets $P,Q$ what is the smallest number $n$ such that any coloring of the elements of the Boolean lattice $B_n$ either admits a monochromatic copy of $P$ or a rainbow copy of $Q$. We consider both weak and strong (non-induced and induced) versions of this problem. We also investigate related problems on (partial) $k$-colorings of $B_n$ that do not admit rainbow antichains of size $k$.

A clique covering of a graph $G$ is a set of cliques of $G$ such that any edge of $G$ is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number $scc(G)$ of a graph $G$, is defined as the smallest possible weight of a clique covering of $G$. Let $ K_t(d) $ denote the complete $ t $-partite graph with each part of size $d$. We prove that for any fixed $d \ge 2$, we have $$\lim_{t \rightarrow \infty} scc(K_t(d))= \frac{d}{2} t\log t.$$ This disproves a conjecture of Davoodi, Javadi and Omoomi.

For a graph $F$, a hypergraph $\mathcal{H}$ is a Berge copy of $F$ (or a Berge-$F$ in short), if there is a bijection $f : E(F) \rightarrow E(\mathcal{H})$ such that for each $e \in E(F)$ we have $e \subset f(e)$. A hypergraph is Berge-$F$-free if it does not contain a Berge copy of $F$. We denote the maximum number of hyperedges in an $n$-vertex $r$-uniform Berge-$F$-free hypergraph by $\mathrm{ex}_r(n,\textrm{Berge-}F).$ In this paper we prove two general lemmas concerning the maximum size of a Berge-$F$-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on $\mathrm{ex}_r(n,\textrm{Berge-}F)$ when $F$ is a path (reproving a result of Gy\H{o}ri, Katona and Lemons), a cycle (extending a result of F\"uredi and \"Ozkahya), a theta graph (improving a result of He and Tait), or a $K_{2,t}$ (extending a result of Gerbner, Methuku and Vizer). We also establish new bounds when $F$ is a clique (which implies extensions of results by Maherani and Shahsiah and by Gy\'arf\'as) and when $F$ is a general tree.

For a graph $G$, a hypergraph $\mathcal{H}$ is a Berge copy of $G$ (or a Berge-$G$ in short), if there is a bijection $f : E(G) \rightarrow E(\mathcal{H})$ such that for each $e \in E(G)$ we have $e \subseteq f(e)$. We denote the family of $r$-uniform hypergraphs that are Berge copies of $G$ by $B^rG$. For families of $r$-uniform hypergraphs $\mathbf{H}$ and $\mathbf{H}'$, we denote by $R(\mathbf{H},\mathbf{H}')$ the smallest number $n$ such that in any blue-red coloring of $\mathcal{K}_n^r$ (the complete $r$-uniform hypergraph on $n$ vertices) there is a monochromatic blue copy of a hypergraph in $\mathbf{H}$ or a monochromatic red copy of a hypergraph in $\mathbf{H}'$. $R^c(\mathbf{H})$ denotes the smallest number $n$ such that in any coloring of the hyperedges of $\mathcal{K}_n^r$ with $c$ colors, there is a monochromatic copy of a hypergraph in $\mathbf{H}$. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if $r> 2c$, then $R^c(B^rK_n)=n$. In the case $r = 2c$, we show that $R^c(B^rK_n)=n+1$, and if $G$ is a non-complete graph on $n$ vertices, then $R^c(B^rG)=n$, assuming $n$ is large enough. In the case $r < 2c$ we also obtain bounds on $R^c(B^rK_n)$. Moreover, we also determine the exact value of $R(B^3T_1,B^3T_2)$ for every pair of trees $T_1$ and $T_2$., Comment: Revised based on the suggestions of the referees

The maximum size of an $r$-uniform hypergraph without a Berge cycle of length at least $k$ has been determined for all $k \ge r+3$ by F\"uredi, Kostochka and Luo and for $k

For a graph $F$, we say a hypergraph $H$ is Berge-$F$ if it can be obtained from $F$ be replacing each edge of $F$ with a hyperedge containing it. We say a hypergraph is Berge-$F$-saturated if it does not contain a Berge-$F$, but adding any hyperedge creates a copy of Berge-$F$. The $k$-uniform saturation number of Berge-$F$, $\mathrm{sat}_k(n,\text{Berge-}F)$ is the fewest number of edges in a Berge-$F$-saturated $k$-uniform hypergraph on $n$ vertices. We show that $\mathrm{sat}_k(n,\text{Berge-}F) = O(n)$ for all graphs $F$ and uniformities $3\leq k\leq 5$, partially answering a conjecture of English, Gordon, Graber, Methuku, and Sullivan. We also extend this conjecture to Berge copies of hypergraphs.

In this short note we consider the oriented vertex Tur\'an problem in the hypercube: for a fixed oriented graph $\overrightarrow{F}$, determine the maximum size $ex_v(\overrightarrow{F}, \overrightarrow{Q_n})$ of a subset $U$ of the vertices of the oriented hypercube $\overrightarrow{Q_n}$ such that the induced subgraph $\overrightarrow{Q_n}[U]$ does not contain any copy of $\overrightarrow{F}$. We obtain the exact value of $ex_v(\overrightarrow{P_k}, \overrightarrow{Q_n})$ for the directed path $\overrightarrow{P_k}$, the exact value of $ex_v(\overrightarrow{V_2}, \overrightarrow{Q_n})$ for the directed cherry $\overrightarrow{V_2}$ and the asymptotic value of $ex_v(\overrightarrow{T}, \overrightarrow{Q_n})$ for any directed tree $\overrightarrow{T}$.

Let $F$ be a fixed graph. The rainbow Tur\'an number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstra\"ete. In this paper, we show that the rainbow Tur\'an number of a path with $k+1$ edges is less than $\left(\frac{9k}{7}+2\right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.

The vertex set of the Kneser graph $K(n,k)$ is $V = \binom{[n]}{k}$ and two vertices are adjacent if the corresponding sets are disjoint. For any graph $F$, the largest size of a vertex set $U \subseteq V$ such that $K(n,k)[U]$ is $F$-free, was recently determined by Alishahi and Taherkhani, whenever $n$ is large enough compared to $k$ and $F$. In this paper, we determine the second largest size of a vertex set $W \subseteq V$ such that $K(n,k)[W]$ is $F$-free, in the case when $F$ is an even cycle or a complete multi-partite graph. In the latter case, we actually give a more general theorem depending on the chromatic number of $F$. These results generalize the celebrated Erd\H os-Ko-Rado theorem and Hilton-Milner theorem., Comment: 12 pages, the proof of Lemma 2.4 is corrected

A subfamily $\{F_1,F_2,\dots,F_{|P|}\}\subseteq \mathcal F$ is a copy of the poset $P$ if there exists a bijection $i:P\rightarrow \{F_1,F_2,\dots,F_{|P|}\}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$. A family $\mathcal F$ is $P$-free, if it does not contain a copy of $P$. In this paper we establish basic results on the maximum possible number of $k$-chains in a $P$-free family $\mathcal F\subseteq 2^{[n]}$. We prove that if the height of $P$, $h(P) > k$, then this number is of the order $\Theta(\prod_{i=1}^{k+1}\binom{l_{i-1}}{l_i})$, where $l_0=n$ and $l_1\ge l_2\ge \dots \ge l_{k+1}$ are such that $n-l_1,l_1-l_2,\dots, l_k-l_{k+1},l_{k+1}$ differ by at most one. On the other hand if $h(P)\le k$, then we show that this number is of smaller order of magnitude. Let $\vee_r$ denote the poset on $r+1$ elements $a, b_1, b_2, \ldots, b_r$, where $a < b_i$ for all $1 \le i \le r$ and let $\wedge_r$ denote its dual. For any values of $k$ and $l$, we construct a $\{\wedge_k,\vee_l\}$-free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of $k$ and $l$. We also derive the asymptotics of the maximum number of copies of certain tree posets $T$ of height 2 in $\{\wedge_k,\vee_l\}$-free families $\mathcal F \subseteq 2^{[n]}$.

Let $F = (U,E)$ be a graph and $\mathcal{H} = (V,\mathcal{E})$ be a hypergraph. We say that $\mathcal{H}$ contains a Berge-$F$ if there exist injections $\psi:U\to V$ and $\varphi:E\to \mathcal{E}$ such that for every $e=\{u,v\}\in E$, $\{\psi(u),\psi(v)\}\subset\varphi(e)$. Let $ex_r(n,F)$ denote the maximum number of hyperedges in an $r$-uniform hypergraph on $n$ vertices which does not contain a Berge-$F$. For small enough $r$ and non-bipartite $F$, $ex_r(n,F)=\Omega(n^2)$; we show that for sufficiently large $r$, $ex_r(n,F)=o(n^2)$. Let $thres(F) = \min\{r_0 :ex_r(n,F) = o(n^2) \text{ for all } r \ge r_0 \}$. We show lower and upper bounds for $thres(F)$, the uniformity threshold of $F$. In particular, we obtain that $thres(\triangle) = 5$, improving a result of Gy\H{o}ri. We also study the analogous problem for linear hypergraphs. Let $ex^L_r(n,F)$ denote the maximum number of hyperedges in an $r$-uniform linear hypergraph on $n$ vertices which does not contain a Berge-$F$, and let the linear unformity threshold $thres^L(F) = \min\{r_0 :ex^L_r(n,F) = o(n^2) \text{ for all } r \ge r_0 \}$. We show that $thres^L(F)$ is equal to the chromatic number of $F$.

Given a graph $H$ and a set of graphs $\mathcal F$, let $ex(n,H,\mathcal F)$ denote the maximum possible number of copies of $H$ in an $\mathcal F$-free graph on $n$ vertices. We investigate the function $ex(n,H,\mathcal F)$, when $H$ and members of $\mathcal F$ are cycles. Let $C_k$ denote the cycle of length $k$ and let $\mathscr C_k=\{C_3,C_4,\ldots,C_k\}$. Some of our main results are the following. (i) We show that $ex(n, C_{2l}, C_{2k}) = \Theta(n^l)$ for any $l, k \ge 2$. Moreover, we determine it asymptotically in the following cases: We show that $ex(n,C_4,C_{2k}) = (1+o(1)) \frac{(k-1)(k-2)}{4} n^2$ and that the maximum possible number of $C_6$'s in a $C_8$-free bipartite graph is $n^3 + O(n^{5/2})$. (ii) Solymosi and Wong proved that if Erd\H{o}s's Girth Conjecture holds, then for any $l \ge 3$ we have $ex(n,C_{2l},\mathscr C_{2l-1})=\Theta(n^{2l/(l-1)})$. We prove that forbidding any other even cycle decreases the number of $C_{2l}$'s significantly: For any $k > l$, we have $ex(n,C_{2l},\mathscr C_{2l-1} \cup \{C_{2k}\})=\Theta(n^2).$ More generally, we show that for any $k > l$ and $m \ge 2$ such that $2k \neq ml$, we have $ex(n,C_{ml},\mathscr C_{2l-1} \cup \{C_{2k}\})=\Theta(n^m).$ (iii) We prove $ex(n,C_{2l+1},\mathscr C_{2l})=\Theta(n^{2+1/l}),$ provided a strong version of Erd\H{o}s's Girth Conjecture holds (which is known to be true when $l = 2, 3, 5$). Moreover, forbidding one more cycle decreases the number of $C_{2l+1}$'s significantly: More precisely, we have $ex(n, C_{2l+1}, \mathscr C_{2l} \cup \{C_{2k}\}) = O(n^{2-\frac{1}{l+1}}),$ and $ex(n, C_{2l+1}, \mathscr C_{2l} \cup \{C_{2k+1}\}) = O(n^2)$ for $l > k \ge 2$. (iv) We also study the maximum number of paths of given length in a $C_k$-free graph, and prove asymptotically sharp bounds in some cases., Comment: 37 Pages; Substantially revised, contains several new results. Mistakes corrected based on the suggestions of a referee

Given two graphs $H$ and $F$, the maximum possible number of copies of $H$ in an $F$-free graph on $n$ vertices is denoted by $ex(n,H,F)$. We investigate the function $ex(n,H,kF)$, where $kF$ denotes $k$ vertex disjoint copies of a fixed graph $F$. Our results include cases when $F$ is a complete graph, cycle or a complete bipartite graph., Comment: 18 pages. There was a wrong statement in the first version, it is corrected now

The maximum size, $La(n,P)$, of a family of subsets of $[n]=\{1,2,...,n\}$ without containing a copy of $P$ as a subposet, has been intensively studied. Let $P$ be a graded poset. We say that a family $\mathcal{F}$ of subsets of $[n]=\{1,2,...,n\}$ contains a \emph{rank-preserving} copy of $P$ if it contains a copy of $P$ such that elements of $P$ having the same rank are mapped to sets of same size in $\mathcal{F}$. The largest size of a family of subsets of $[n]=\{1,2,...,n\}$ without containing a rank-preserving copy of $P$ as a subposet is denoted by $La_{rp}(n,P)$. Clearly, $La(n,P) \le La_{rp}(n,P)$ holds. In this paper we prove asymptotically optimal upper bounds on $La_{rp}(n,P)$ for tree posets of height $2$ and monotone tree posets of height $3$, strengthening a result of Bukh in these cases. We also obtain the exact value of $La_{rp}(n,\{Y_{h,s},Y_{h,s}'\})$ and $La(n,\{Y_{h,s},Y_{h,s}'\})$, where $Y_{h,s}$ denotes the poset on $h+s$ elements $x_1,\dots,x_h,y_1,\dots,y_s$ with $x_1<\dots

In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.