Search

Let $f_{F,G}(n)$ be the largest size of an induced $F$-free subgraph that every $n$-vertex $G$-free graph is guaranteed to contain. We prove that for any triangle-free graph $F$, \[ f_{F,K_3}(n) = f_{K_2,K_3}(n)^{1 + o(1)} = n^{\frac{1}{2} + o(1)}.\] Along the way we give a slight improvement of a construction of Erd\H os-Frankl-R\"odl for the Brown-Erd\H os-S\'os $(3r-3,3)$-problem when $r$ is large. In contrast to our result for $K_3$, for any $K_4$-free graph $F$ containing a cycle, we prove there exists $c_F > 0$ such that $$f_{F,K_4}(n) > f_{K_2,K_4}(n)^{1 + c_F} = n^{\frac{1}{3}+c_F+o(1)}.$$ \iffalse We also observe that our earlier proof for $F=K_3$ generalizes to $f_{F,K_4}(n) = O(\sqrt{n}\log n)$ for all $F$ containing a cycle. \fi For every graph $G$, we prove that there exists $\varepsilon_G >0$ such that whenever $F$ is a non-empty graph such that $G$ is not contained in any blowup of $F$, then $f_{F,G}(n) = O(n^{1-\varepsilon_G})$. On the other hand, for graph $G$ that is not a clique, and every $\varepsilon>0$, we exhibit a $G$-free graph $F$ such that $f_{F,G}(n) = \Omega(n^{1-\varepsilon})$.

Let $ES_{\ell}(n)$ be the minimum $N$ such that every $N$-element point set in the plane contains either $\ell$ collinear members or $n$ points in convex position. We prove that there is a constant $C>0$ such that, for each $\ell, n \ge 3$, $$ (3\ell - 1) \cdot 2^{n-5} < ES_{\ell}(n) < \ell^2 \cdot 2^{n+ C\sqrt{n\log n}}.$$ A similar extension of the well-known Erd\H os--Szekeres cups-caps theorem is also proved.

Answering a question of Erd\H{o}s and Graham, we show that for each fixed positive rational number $x$ the number of ways to write $x$ as a sum of reciprocals of distinct positive integers each at most $n$ is $2^{(c_x + o(1))n}$ for an explicit constant $c_x$ increasing with $x$., Comment: 8 pages

A fundamental problem in Ramsey theory is to determine the growth rate in terms of $n$ of the Ramsey number $r(H, K_n^{(3)})$ of a fixed $3$-uniform hypergraph $H$ versus the complete $3$-uniform hypergraph with $n$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $H$, including links of odd cycles and tight cycles of length not divisible by three, $r(H, K_n^{(3)}) \ge 2^{\Omega_H(n \log n)}$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $H$ for which $r(H, K_n^{(3)})$ is superpolynomial in $n$. This provides the first example of a separation between $r(H,K_n^{(3)})$ and $r(H,K_{n,n,n}^{(3)})$, since the latter is known to be polynomial in $n$ when $H$ is linear., Comment: 22 pages

For an integer $n \geq 1$, the Erd\H{o}s-Rogers function $f_{s}(n)$ is the maximum integer $m$ such that every $n$-vertex $K_{s+1}$-free graph has a $K_s$-free subgraph with $m$ vertices. It is known that for all $s \geq 3$, $f_{s}(n) = \Omega(\sqrt{n\log n}/\log \log n)$ as $n \rightarrow \infty$. In this paper, we show that for all $s \geq 3$, \begin{equation*} f_{s}(n) = O(\sqrt{n}\, \log n). \end{equation*} This improves previous bounds of order $\sqrt{n} (\log n)^{2(s + 1)^2}$ by Dudek, Retter and R\"{o}dl., Comment: 8 pages, 2 figures

Building on recent work of Mattheus and Verstra\"ete, we establish a general connection between Ramsey numbers of the form $r(F,t)$ for $F$ a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an $m$ by $n$ $0/1$-matrix that does not have any matrix from a fixed finite family $\mathcal{L}(F)$ derived from $F$ as a submatrix. As an application, we give new lower bounds for the Ramsey numbers $r(C_5,t)$ and $r(C_7,t)$, namely, $r(C_5,t) = \tilde\Omega(t^{\frac{10}{7}})$ and $r(C_7,t) = \tilde\Omega(t^{\frac{5}{4}})$. We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of $r(C_{2\ell+1}, t)$ for any fixed integer $\ell \geq 2$., Comment: 9 pages

For integers $s,t \geq 2$, the Ramsey numbers $r(s,t)$ denote the minimum $N$ such that every $N$-vertex graph contains either a clique of order $s$ or an independent set of order $t$. In this paper we prove \[ r(4,t) = \Omega\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty\] which determines $r(4,t)$ up to a factor of order $\log^2 \! t$, and solves a conjecture of Erd\H{o}s., Comment: Updated journal version

We consider the maximum chromatic number of hypergraphs consisting of cliques that have pairwise small intersections. Designs of the appropriate parameters produce optimal constructions, but these are known to exist only when the number of cliques is exponential in the clique size. We construct near designs where the number of cliques is polynomial in the clique size, and show that they have large chromatic number. The case when the cliques have pairwise intersections of size at most one seems particularly challenging. Here we give lower bounds by analyzing a random greedy hypergraph process. We also consider the related question of determining the maximum number of caps in a finite projective/affine plane and obtain nontrivial upper and lower bounds.

A $(k; r, s; n, q)$-set (short: $(r,s)$-set) of $\mathrm{PG}(n, q)$ is a set of points $X$ with $|X| = k$ such that no $s$-space contains more than $r$ points of $X$. We investigate the asymptotic size of $(r, s)$-sets for $n$ fixed and $q \rightarrow \infty$. In particular, we show the existence of $(3, 2)$-sets of size $(1+o(1)) q^{3/2}$ for $n=6$, $(4, 2)$-sets of size $(1+o(1)) q^{\frac{n-1}{2}}$, and $(9, 2)$-sets of size $(1+o(1)) q^2$ for $n=4$. We also generalize a bound by Rao from 1947 and show that an $(r,s)$-set has size at most $O(q^{\frac{n-e+1}{e}})$ if there exist integers $d,e \geq 2$ such that $s=d(e-1)$ and $r=de-1$., Comment: 10 pages, removed the part on random polynomials which duplicated recent work by Sudakov and Tomon

Let $K_m^{(3)}$ denote the complete $3$-uniform hypergraph on $m$ vertices and $S_n^{(3)}$ the $3$-uniform hypergraph on $n+1$ vertices consisting of all $\binom{n}{2}$ edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off-diagonal Ramsey number $r(K_{4}^{(3)},S_n^{(3)})$ exhibits an unusual intermediate growth rate, namely, \[ 2^{c \log^2 n} \le r(K_{4}^{(3)},S_n^{(3)}) \le 2^{c' n^{2/3}\log n} \] for some positive constants $c$ and $c'$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum $N$ such that any $2$-edge-coloring of the Cartesian product $K_N \square K_N$ contains either a red rectangle or a blue $K_n$?, Comment: 13 pages

For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{\Theta(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erd\H{o}s and Szemer\'edi, who treated the case $s = r-1$, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs., Comment: 11 pages

A set of geometric graphs is {\em geometric-packable} if it can be asymptotically packed into every sequence of drawings of the complete graph $K_n$. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When $G$ is the $4$-cycle (or $4$-cycle with a chord), we show that the set of plane drawings of $G$ is geometric-packable. In contrast, the analogous statement is false when $G$ is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is {\em convex-packable} if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph $G$, we determine whether or not a plane $G$ is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of $K_n$.

In this paper, we consider an extension of cycle-complete graph Ramsey numbers to Berge cycles in hypergraphs: for $k \geq 2$, a {\em non-trivial Berge $k$-cycle} is a family of sets $e_1,e_2,\dots,e_k$ such that $e_1 \cap e_2, e_2 \cap e_3,\dots,e_k \cap e_1$ has a system of distinct representatives and $e_1 \cap e_2 \cap \dots \cap e_k = \emptyset$. In the case that all the sets $e_i$ have size three, let $\mathcal{B}_k$ denotes the family of all non-trivial Berge $k$-cycles. The {\em Ramsey numbers} $R(t,\mathcal{B}_k)$ denote the minimum $n$ such that every $n$-vertex $3$-uniform hypergraph contains either a non-trivial Berge $k$-cycle or an independent set of size $t$. We prove \[ R(t, \mathcal{B}_{2k}) \leq t^{1 + \frac{1}{2k-1} + \frac{4}{\sqrt{\log t}}}\] and moreover, we show that if a conjecture of Erd\H{o}s and Simonovits \cite{ES} on girth in graphs is true, then this is tight up to a factor $t^{o(1)}$ as $t \rightarrow \infty$.

For an $r$-uniform hypergraph $H$ and a family of $r$-uniform hypergraphs $\mathcal{F}$, the relative Tur\'{a}n number $\mathrm{ex}(H,\mathcal{F})$ is the maximum number of edges in an $\mathcal{F}$-free subgraph of $H$. In this paper we give lower bounds on $\mathrm{ex}(H,\mathcal{F})$ for certain families of hypergraph cycles $\mathcal{F}$ such as Berge cycles and loose cycles. In particular, if $\mathcal{C}_\ell^3$ denotes the set of all $3$-uniform Berge $\ell$-cycles and $H$ is a 3-uniform hypergraph with maximum degree $\Delta$, we prove \[\mathrm{ex}(H,\mathcal{C}_4^{3})\ge \Delta^{-3/4-o(1)}e(H),\] \[\mathrm{ex}(H,\mathcal{C}_5^{3})\ge \Delta^{-3/4-o(1)}e(H),\] and these bounds are tight up to the $o(1)$ term., Comment: 20 pages, minor typos corrected, to appear in Discrete Mathematics

For integers $2 \leq t \leq k$, we consider a collection of $k$ set families $\mathcal{A}_j: 1 \leq j \leq k$ where $\mathcal{A}_j = \{ A_{j,i} \subseteq [n] : 1 \leq i \leq m \}$ and $|A_{1, i_1} \cap \cdots \cap A_{k,i_k}|$ is even if and only if at least $t$ of the $i_j$ are distinct. In this paper, we prove that $m =O(n^{ 1/ \lfloor k/2 \rfloor})$ when $t=k$ and $m = O( n^{1/(t-1)})$ when $2t-2 \leq k$ and prove that both of these bounds are best possible. Specializing to the case where $\mathcal{A} = \mathcal{A}_1 = \cdots = \mathcal{A}_k$, we recover a variation of the classical oddtown problem.

A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cgh's consisting of two disjoint triples. These were studied at length by Bra{\ss} (2004) and by Aronov, Dujmovi\'c, Morin, Ooms, and da Silveira (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of $n$ points in the plane., Comment: Supersedes version 1 significantly. Only a new reference were given to version 2 (and the linear term in Thm 6 was also calculated). 25 pages, 16 figures

Morris and Saxton used the method of containers to bound the number of $n$-vertex graphs with $m$ edges containing no $\ell$-cycles, and hence graphs of girth more than $\ell$. We consider a generalization to $r$-uniform hypergraphs. The {\em girth} of a hypergraph $H$ is the minimum $\ell$ such that for some $F \subseteq H$, there exists a bijection $\phi : E(C_\ell) \to E(F)$ with $e\subseteq \phi(e)$ for all $e\in E(C_\ell)$. Letting $N_m^r(n,\ell)$ denote the number of $n$-vertex $r$-uniform hypergraphs with $m$ edges and girth larger than $\ell$ and defining $\lambda = \lceil (r - 2)/(\ell - 2)\rfloor$, we show \[ N_m^r(n,\ell) \leq N_m^2(n,\ell)^{r - 1 + \lambda}\] which is tight when $\ell - 2 $ divides $r - 2$ up to a $1 + o(1)$ term in the exponent. This result is used to address the extremal problem for subgraphs of girth more than $\ell$ in random $r$-uniform hypergraphs., Comment: Extended Theorem 1.3 to all r and corrected various minor errors and typos. To appear in Journal of Graph Theory

For two graphs $F$ and $H$, the relative Tur\'{a}n number $\mathrm{ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau \cite{FKP} and Perarnau and Reed \cite{PR} studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, \[\mathrm{ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).\] This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that $\mathrm{ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij \cite{BS} and Morris and Saxton \cite{MS}., Comment: 22 pages

In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $\alpha(G)\geq (f(d,r)-\epsilon(g,d,r))n$, where $\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$. We prove that if $H$ is an $n$-vertex $r$-uniform hypergraph with maximum degree $\triangle$, then as $\triangle \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph of $H$ is at least \[ \frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.\] For $r = 3$, this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$-vertex triple system with edge-probability $p$ such that $pn^3\rightarrow\infty$ as $n\rightarrow\infty$, then with high probability as $n \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph is \[ \min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.\] We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemer\'{e}di., Comment: Small typos were corrected

In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Tur\'an numbers of hypergraphs in the Erd\H{o}s--Ko--Rado range. An $(a,b)$-path $P$ of length $2k-1$ consists of $2k-1$ sets of size $r=a+b$ as follows. Take $k$ pairwise disjoint $a$-element sets $A_0, A_2, \dots, A_{2k-2}$ and other $k$ pairwise disjoint $b$-element sets $B_1, B_3, \dots, B_{2k-1}$ and order them linearly as $A_0, B_1, A_2, B_3, A_4\dots$. Define the (hyper)edges of $P_{2k-1}(a,b)$ as the sets of the form $A_i\cup B_{i+1}$ and $B_j\cup A_{j+1}$. The members of $P$ can be represented as $r$-element intervals of the $ak+bk$ element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed $k,a,b$, as $n\to \infty$ \[ {\rm ex}_r(n,P_{2k-1}(a,b)) = (k - 1){n \choose r - 1} + o(n^{r - 1}).\] This generalizes the Erd\H{o}s--Gallai theorem for graphs which is the case of $a=b=1$. We also determine the asymptotics when $a+b$ is even; the remaining cases are still open., Comment: 17 pages, 6 figures

In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erd\H{o}s-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Tur\'an problem for tight paths in uniform hypergraphs., Comment: 14 pages, 3 figures

A classical result by Erd\H{o}s, and later on by Bondy and Simonivits, states that every $n$-vertex graph with no cycle of length $2k$ has at most $O(n^{1+1 /k})$ edges. This bound is known to be tight when $k \in \{2,3,5\},$ but it is a major open problem in extremal graph theory to decide if this bound is tight for all $k$. In this paper, we study the effect of forbidding short even cycles in incidence graphs of point-line arrangements in the plane. It is not known if the Erd\H{o}s upper bound stated above can be improved to $o(n^{1+1/k})$ in this geometric setting, and in this note, we establish non-trivial lower bounds for this problem by modifying known constructions arising in finite geometries. In particular, by modifying a construction due to Labeznik and Ustimenko, we construct an arrangement of $n$ points and $n$ lines in the plane, such that their incidence graph has girth at least $k + 5$, and determines at least $\Omega({n^{1+\frac{4}{k^2+6k-3}}})$ incidences. We also apply the same technique to Wenger graphs, which gives a better lower bound for $k=5.$

For an integer $d \geq 2$, a family $\mathcal{F}$ of sets is $\textit{$d$-wise intersecting}$ if for any distinct sets $A_1,A_2,\dots,A_d \in \mathcal{F}$, $A_1 \cap A_2 \cap \dots \cap A_d \neq \emptyset$, and $\textit{non-trivial}$ if $\bigcap \mathcal{F} = \emptyset$. Hilton and Milner conjectured that for $k \geq d \geq 2$ and large enough $n$, the extremal non-trivial $d$-wise intersecting family of $k$-element subsets of $[n]$ is one of the following two families: \begin{align*} &\mathcal{H}(k,d) = \{A \in \binom{[n]}{k} : [d-1] \subset A, A \cap [d,k+1] \neq \emptyset\} \cup \{[k+1] \setminus \{i \} : i \in [d - 1]\} \\ &\mathcal{A}(k,d) = \{ A \in \binom{[n]}{k} : |A \cap [d+1]| \geq d \}. \end{align*} The celebrated Hilton-Milner Theorem states that $\mathcal{H}(k,2)$ is the unique extremal non-trivial intersecting family for $k>3$. We prove the conjecture and prove a stability theorem, stating that any large enough non-trivial $d$-wise intersecting family of $k$-element subsets of $[n]$ is a subfamily of $\mathcal{A}(k,d)$ or $\mathcal{H}(k,d)$.

For fixed $s \ge 3$, we prove that if optimal $K_s$-free pseudorandom graphs exist, then the Ramsey number $r(s,t) = t^{s-1+o(1)}$ as $t \rightarrow \infty$. Our method also improves the best lower bounds for $r(C_{\ell},t)$ obtained by Bohman and Keevash from the random $C_{\ell}$-free process by polylogarithmic factors for all odd $\ell \geq 5$ and $\ell \in \{6,10\}$. For $\ell = 4$ it matches their lower bound from the $C_4$-free process. We also prove, via a different approach, that $r(C_5, t)> (1+o(1))t^{11/8}$ and $r(C_7, t)> (1+o(1))t^{11/9}$. These improve the exponent of $t$ in the previous best results and appear to be the first examples of graphs $F$ with cycles for which such an improvement of the exponent for $r(F, t)$ is shown over the bounds given by the random $F$-free process and random graphs., Comment: 10 pages, minor changes to the first version

An ordered hypergraph is a hypergraph whose vertex set is linearly ordered, and a convex geometric hypergraph is a hypergraph whose vertex set is cyclically ordered. Extremal problems for ordered and convex geometric graphs have a rich history with applications to a variety of problems in combinatorial geometry. In this paper, we consider analogous extremal problems for uniform hypergraphs, and determine the order of magnitude of the extremal function for various ordered and convex geometric paths and matchings. Our results generalize earlier works of Bra{\ss}-K\'{a}rolyi-Valtr, Capoyleas-Pach and Aronov-Dujmovi\v{c}-Morin-Ooms-da Silveira. We also provide a new generalization of the Erd\H os-Ko-Rado theorem in the ordered setting., Comment: 19 pages 2 figures. arXiv admin note: substantial text overlap with arXiv:1807.05104

An {\em ordered $r$-graph} is an $r$-uniform hypergraph whose vertex set is linearly ordered. Given $2\leq k\leq r$, an ordered $r$-graph $H$ is {\em interval} $k$-{\em partite} if there exist at least $k$ disjoint intervals in the ordering such that every edge of $H$ has nonempty intersection with each of the intervals and is contained in their union. Our main result implies that for each $\alpha > k - 1$ and $d>0$, every $n$-vertex ordered $r$-graph with $d \,n^{\alpha}$ edges has for some $m\leq n$ an $m$-vertex interval $k$-partite subgraph with $\Omega(d\, m^{\alpha})$ edges. This is an extension to ordered $r$-graphs of the observation by Erd\H os and Kleitman that every $r$-graph contains an $r$-partite subgraph with a constant proportion of the edges. The restriction $\alpha > k-1$ is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs., Comment: 16 pages

The extremal functions $ex_{\rightarrow}(n,F)$ and $ex_{\cir}(n,F)$ for ordered and convex geometric acyclic graphs $F$ have been extensively investigated by a number of researchers. Basic questions are to determine when $ex_{\rightarrow}(n,F)$ and $ex_{\cir}(n,F)$ are linear in $n$, the latter posed by Bra\ss-K\'arolyi-Valtr in 2003. In this paper, we answer both these questions for every tree $F$. We give a forbidden subgraph characterization for a family $\cal T$ of ordered trees with $k$ edges, and show that $ex_{\rightarrow}(n,T) = (k - 1)n - {k \choose 2}$ for all $n \geq k + 1$ when $T \in {\cal T}$ and $ex_{\rightarrow}(n,T) = \Omega(n\log n)$ for $T \not\in {\cal T}$. We also describe the family of the convex geometric trees with linear Tur\' an number and show that for every convex geometric tree $F$ not in this family, $ex_{\cir}(n,F)= \Omega(n\log \log n)$., Comment: 14 pages, 9 figures. Same as the first version. Only metadata has been changed

The Bollob\'as set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $n \geq k \geq t \geq 2$, we consider a collection of $k$ families $\mathcal{A}_i: 1 \leq i \leq k$ where $\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$ so that $A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \emptyset $ if and only if there are at least $t$ distinct indices $i_1,i_2,\dots,i_k$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $\beta_{k,t}(n)$ of the families with ground set $[n]$., Comment: Revised writing from previous version

A tight $r$-tree $T$ is an $r$-uniform hypergraph that has an edge-ordering $e_1, e_2, \dots, e_t$ such that for each $i\geq 2$, $e_i$ has a vertex $v_i$ that does not belong to any previous edge and $e_i-v_i$ is contained in $e_j$ for some $j

An ordered hypergraph is a hypergraph whose vertex set is linearly ordered, and a convex geometric hypergraph is a hypergraph whose vertex set is cyclically ordered. Extremal problems for ordered and convex geometric graphs have a rich history with applications to a variety of problems in combinatorial geometry. In this paper, we consider analogous extremal problems for uniform hypergraphs, and discover a general partitioning phenomenon which allows us to determine the order of magnitude of the extremal function for various ordered and convex geometric hypergraphs. A special case is the ordered $n$-vertex $r$-graph $F$ consisting of two disjoint sets $e$ and $f$ whose vertices alternate in the ordering. We show that for all $n \geq 2r + 1$, the maximum number of edges in an ordered $n$-vertex $r$-graph not containing $F$ is exactly \[ {n \choose r} - {n - r \choose r}.\] This could be considered as an ordered version of the Erd\H{o}s-Ko-Rado Theorem, and generalizes earlier results of Capoyleas and Pach and Aronov-Dujmovi\v{c}-Morin-Ooms-da Silveira., Comment: 16 pages, 2 figures

An $r$-uniform hypergraph is a tight $r$-tree if its edges can be ordered so that every edge $e$ contains a vertex $v$ that does not belong to any preceding edge and the set $e-v$ lies in some preceding edge. A conjecture of Kalai [Kalai], generalizing the Erd\H{o}s-S\'os Conjecture for trees, asserts that if $T$ is a tight $r$-tree with $t$ edges and $G$ is an $n$-vertex $r$-uniform hypergraph containing no copy of $T$ then $G$ has at most $\frac{t-1}{r}\binom{n}{r-1}$ edges. A trunk $T'$ of a tight $r$-tree $T$ is a tight subtree such that every edge of $T-T'$ has $r-1$ vertices in some edge of $T'$ and a vertex outside $T'$. For $r\ge 3$, the only nontrivial family of tight $r$-trees for which this conjecture has been proved is the family of $r$-trees with trunk size one in [FF] from 1987. Our main result is an asymptotic version of Kalai's conjecture for all tight trees $T$ of bounded trunk size. This follows from our upper bound on the size of a $T$-free $r$-uniform hypergraph $G$ in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight $r$-trees with at most four edges. In particular, for $3$-uniform hypergraphs, our result on the tight path of length $4$ implies the intersection shadow theorem of Katona [Katona]., Comment: 14 pages

In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz, Sutherland, Kupitz and Perles for convex geometric graphs, as well as the classical Erd\H{o}s-Gallai Theorem for graphs. As a consequence, we obtain the first substantial improvement on the Tur\'{a}n problem for tight paths in uniform hypergraphs., Comment: Present version: 12 pages, 3 figures. We improve results and presentation of an earlier version, and removed results on crossing paths and matchings which will appear in a forthcoming paper

The Erd\H{o}s--Gallai Theorem states that for $k \geq 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k-1)(n-1)$ edges. A stronger version of the Erd\H{o}s--Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e(G) \leq \max\{h(n,k,2),h(n,k,\lfloor \frac{k-1}{2}\rfloor)\}$, where $h(n,k,a) := {k - a \choose 2} + a(n - k + a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,\lfloor \frac{k-1}{2}\rfloor)$ edges. In this paper, we complete a stability theorem which strengthens Kopylov's result. In particular, we show that for $k \geq 3$ odd and all $n \geq k$, every $n$-vertex $2$-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e(G) \leq \max\{h(n,k,3),h(n,k,\frac{k-3}{2})\}$. The upper bound for $e(G)$ here is tight.

Burr and Erd\H{o}s conjectured that for each $k,\ell \in \mathbb Z^+$ such that $k \mathbb Z + \ell$ contains even integers, there exists $c_k(\ell)$ such that any graph of average degree at least $c_k(\ell)$ contains a cycle of length $\ell$ mod $k$. This conjecture was proved by Bollob\'{a}s, and many successive improvements of upper bounds on $c_k(\ell)$ appear in the literature. In this short note, for $1 \leq \ell \leq k$, we show that $c_k(\ell)$ is proportional to the largest average degree of a $C_{\ell}$-free graph on $k$ vertices, which determines $c_k(\ell)$ up to an absolute constant. In particular, using known results on Tur\'{a}n numbers for even cycles, we obtain $c_k(\ell) = O(\ell k^{2/\ell})$ for all even $\ell$, which is tight for $\ell \in \{4,6,10\}$. Since the complete bipartite graph $K_{\ell - 1,n - \ell + 1}$ has no cycle of length $2\ell$ mod $k$, it also shows $c_k(\ell) = \Theta(\ell)$ for $\ell = \Omega(\log k)$., Comment: 10 pages

Let $T$ be a tree with $t$ edges. We show that the number of isomorphic (labeled) copies of $T$ in a graph $G = (V,E)$ of minimum degree at least $t$ is at least \[2|E| \prod_{v \in V} (d(v) - t + 1)^{\frac{(t-1)d(v)}{2|E|}}.\] Consequently, any $n$-vertex graph of average degree $d$ and minimum degree at least $t$ contains at least $$nd(d-t+1)^{t-1}$$ isomorphic (labeled) copies of $T$. This answers a question of Dellamonica et. al. (where the above statement was proved when $T$ is the path with three edges) while extending an old result of Erd\H os and Simonovits.

The Erd\H{o}s-Gallai Theorem states that for $k \geq 2$, every graph of average degree more than $k - 2$ contains a $k$-vertex path. This result is a consequence of a stronger result of Kopylov: if $k$ is odd, $k=2t+1\geq 5$, $n \geq (5t-3)/2$, and $G$ is an $n$-vertex $2$-connected graph with at least $h(n,k,t) := {k-t \choose 2} + t(n -k+ t)$ edges, then $G$ contains a cycle of length at least $k$ unless $G = H_{n,k,t} := K_n - E(K_{n - t})$. In this paper we prove a stability version of the Erd\H{o}s-Gallai Theorem: we show that for all $n \geq 3t > 3$, and $k \in \{2t+1,2t + 2\}$, every $n$-vertex 2-connected graph $G$ with $e(G) > h(n,k,t-1)$ either contains a cycle of length at least $k$ or contains a set of $t$ vertices whose removal gives a star forest. In particular, if $k = 2t + 1 \neq 7$, we show $G \subseteq H_{n,k,t}$. The lower bound $e(G) > h(n,k,t-1)$ in these results is tight and is smaller than Kopylov's bound $h(n,k,t)$ by a term of $n-t-O(1)$., Comment: Dedicated to the memory of G. N. Kopylov, 28 pages. Version 2 differs from Version 1 only in improved presentation

The $r$-expansion $G^+$ of a graph $G$ is the $r$-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a vertex subset of size $r-2$ disjoint from $V(G)$ such that distinct edges are enlarged by disjoint subsets. Let $ex_r(n,F)$ denote the maximum number of edges in an $r$-uniform hypergraph with $n$ vertices not containing any copy of the $r$-uniform hypergraph $F$. Many problems in extremal set theory ask for the determination of $ex_r(n,G^+)$ for various graphs $G$. We survey these Tur\'an-type problems, focusing on recent developments.

Let $G=(V,E)$ be a graph of density $p$ on $n$ vertices. Following Erd\H{o}s, \L uczak and Spencer, an $m$-vertex subgraph $H$ of $G$ is called {\em full} if $H$ has minimum degree at least $p(m - 1)$. Let $f(G)$ denote the order of a largest full subgraph of $G$. If $p\binom{n}{2}$ is a non-negative integer, define \[ f(n,p) = \min\{f(G) : \vert V(G)\vert = n, \ \vert E(G)\vert = p\binom{n}{2} \}.\] Erd\H{o}s, \L uczak and Spencer proved that for $n \geq 2$, \[ (2n)^{\frac{1}{2}} - 2 \leq f(n, {\frac{1}{2}}) \leq 4n^{\frac{2}{3}}(\log n)^{\frac{1}{3}}.\] In this paper, we prove the following lower bound: for $n^{-\frac{2}{3}}