A new stability theorem for the expansion of cliques
0
Citation
0
Reference
20
Related Paper
Abstract:
Let $\ell \ge r\ge 3$. The $r$-graph $H_{\ell+1}^{r}$ is the hypergraph obtained from $K_{\ell+1}$ by adding a set of $r-2$ new vertices to each edge. Using a stability result for $H_{\ell+1}^{r}$, Pikhurko determined ${\rm ex}(n,H_{\ell+1}^{r})$ for sufficiently large $n$. We prove a new type of stability theorem for $H_{\ell+1}^{r}$ that goes beyond this result, and determine the structure of $H_{\ell+1}^{r}$-free hypergraphs $\mathcal{H}$ that satisfy a certain inequality involving the sizes of $\mathcal{H}$ and its shadow $\partial\mathcal{H}$. Our result can be viewed as an extension of a stability theorem of Keevash about the Kruskal-Katona theorem to $H_{\ell+1}^{r}$-free hypergraphs.Keywords:
Hypergraph
Stability theorem
Structured program theorem
Cite
Infinity
Constant (computer programming)
Cite
Citations (3)
Hypergraph
Cite
Citations (32)
Hypergraph
Cite
Citations (4)
Hypergraph
Infimum and supremum
Cite
Citations (9)
For $k,n\in \mathbb{N}$, the Kneser graph $K(n,k)$ is the graph with vertex set $V=[n]^{(k)}$ and edge set $E=\{\{x,y\} \in V^{(2)}: x\cap y=\emptyset\}$. Chen proved that for $n\geq 3k$, Kneser graphs are Hamiltonian. Similarly as for graphs with Hajnal's and Szemeredi's result about a minimum degree condition for clique factors and the Posa-Seymour Conjecture together with its solution for large graphs due to Komlos, Sarkozy, and Szemeredi, the next step is to ask for clique factors and powers of Hamiltonian cycles in Kneser graphs. For $k,\ell\in \mathbb{N}$, let $n(k,\ell)$ be the smallest integer such that for $n\geq n(k,\ell)$, $K(n,k)$ contains the $\ell$-th power of a Hamiltonian cycle. Katona conjectured that for all but finitely many exceptions, $n(k,\ell)=(\ell+1)k+1$ holds. In particular, it would be interesting to know whether $n(k,\ell)$ is linear in $k$ (for fixed $\ell$). So far this is not known for $k\geq 2$. In this note, we take a first step towards such a linear bound by proving that for $\ell\in \mathbb{N}$, $k\geq \ell$ and $n\geq \ell ^3k$, all but at most $\ell-1$ vertices of $K(n,k)$ can be partitioned into cliques of size $\ell$.
Further, we use our methods to extend a short proof due to Chen and Furedi that $K(n,k)$ is Hamiltonian for $n\geq 3k$ and $k \mid n$ to all $n\geq 4k$ if $k\geq 4$.
Clique number
Clique
Cite
Citations (0)
For fixed positive integers $r, k$ and $\ell$ with $1 \leq \ell < r$ and an $r$-uniform hypergraph $H$, let $κ(H, k,\ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $\ell$ elements. Consider the function $\KC(n,r,k,\ell)=\max_{H\in{\mathcal H}_{n}} κ(H, k,\ell) $, where the maximum runs over the family ${\mathcal H}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $\KC(n,r,k,\ell)$ for every fixed $r$, $k$ and $\ell$ and describe the extremal hypergraphs. This variant of a problem of Erdős and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdős--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {\bf 12} (1961), 313--320].
Cite
Citations (2)
The Erd\H{o}s--Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph $H$, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of $r$-uniform hypergraphs.
A theorem of R\odl asserts that if an $n$-vertex graph is non-universal then it contains an almost homogeneous set (i.e one with edge density either very close to $0$ or $1$) of size $\Omega(n)$. We prove that if a $3$-uniform hypergraph is non-universal then it contains an almost homogeneous set of size $\Omega(\log n)$. An example of R\odl from 1986 shows that this bound is tight.
Let $R_r(t)$ denote the size of the largest non-universal $r$-graph $G$ so that neither $G$ nor its complement contain a complete $r$-partite subgraph with parts of size $t$. We prove an Erd\H{o}s--Hajnal-type stepping-up lemma, showing how to transform a lower bound for $R_{r}(t)$ into a lower bound for $R_{r+1}(t)$. As an application of this lemma, we improve a bound of Conlon--Fox--Sudakov by showing that $R_3(t) \geq t^{\Omega(t)}$.
Hypergraph
Lemma (botany)
Cite
Citations (0)
It is conjectured by Frankl and Füredi that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${\mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform hypergraphs with $m$ edges in \cite{FF}. Motzkin and Straus' theorem confirms this conjecture when $r=2$. For $r=3$, it is shown by Talbot in \cite{T} that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $r$-uniform hypergraphs. As an implication of this connection, we prove that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${\mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform graphs with $t$ vertices and $m$ edges satisfying ${t-1\choose r}\leq m \leq {t-1\choose r}+ {t-2\choose r-1}-[(2r-6)\times2^{r-1}+2^{r-3}+(r-4)(2r-7)-1]({t-2\choose r-2}-1)$ for $r\geq 4.$
Hypergraph
Clique
Cite
Citations (0)
Given a family $\mathcal{F}$ of bipartite graphs, the {\it Zarankiewicz number} $z(m,n,\mathcal{F})$ is the maximum number of edges in an $m$ by $n$ bipartite graph $G$ that does not contain any member of $\mathcal{F}$ as a subgraph (such $G$ is called {\it $\mathcal{F}$-free}). For $1\leq \beta<\alpha<2$, a family $\mathcal{F}$ of bipartite graphs is $(\alpha,\beta)$-{\it smooth} if for some $\rho>0$ and every $m\leq n$, $z(m,n,\mathcal{F})=\rho m n^{\alpha-1}+O(n^\beta)$. Motivated by their work on a conjecture of Erd\H{o}s and Simonovits on compactness and a classic result of Andr\'asfai, Erd\H{o}s and S\'os, in \cite{AKSV} Allen, Keevash, Sudakov and Verstra\"ete proved that for any $(\alpha,\beta)$-smooth family $\mathcal{F}$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\rho(\frac{2n}{5}+o(n))^{\alpha-1}$ is bipartite. In this paper, we strengthen their result by showing that for every real $\delta>0$, there exists $k_0$ such that for all odd $k\geq k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup\{C_k\}$-free graph with minimum degree at least $\delta n^{\alpha-1}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families $\mathcal{F}$ consisting of the single graph $K_{s,t}$ when $t\gg s$. We also prove an analogous result for $C_{2\ell}$-free graphs for every $\ell\geq 2$, which complements a result of Keevash, Sudakov and Verstra\"ete in \cite{KSV}.
Degree (music)
Complete bipartite graph
Cite
Citations (0)
Let $G$ be a graph and $H\colon V(G)\to 2^\mathbb{N}$ a set function associated with $G$. A spanning subgraph $F$ of $G$ is called an $H$-factor if the degree of any vertex $v$ in $F$ belongs to the set $H(v)$. This paper contains two results on the existence of $H$-factors in regular graphs. First, we construct an $r$-regular graph without some given $H^*$-factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lovász's characterization theorem on the existence of $(g, f)$-factors, we find a sharp condition for the existence of general $H$-factors in $\{r, r+1\}$-graphs in terms of the maximum and minimum of $H$. This result reduces to Thomassen's theorem for the case that $H(v)$ consists of the same two consecutive integers for all vertices $v$ and to Tutte's theorem if the graph is regular in addition.
Cite
Citations (4)