Tura\'an density of an $r$-uniform hypergraph $H$.

27 Views Asked by At

The Tur'an density of an $r$-uniform hypergraph $H$ is $$\lim\limits_{n\rightarrow\infty}\frac{ex(n,H)}{n\choose r}$$.

It is known that this is well defined. To prove this, it is enough to show that the sequence $$\left\{\frac{ex(n,H)}{n\choose r}\right\}$$ is a decreasing sequence. I want to prove this statement. I start my argument this way. Let $G$ be an $(n+1)$-vertex, $H$-free and $r$-uniform hypergraph such that $e(G)=ex(n+1,H)$. Then deleting a vertex from $G$, results an $r$-uniform $H$-free hypergraph, and hence $$\sum\limits_{|V(U)|=n}e(u)\leq (n+1)ex(n,H),$$ and hence an upper bound $\sum\limits_{|V(U)|=n}e(u)$ is found. If I can verify that $$(n+1-r)e(G)=\sum\limits_{|V(U)|=n}e(u),$$ then obviously I can get the inequality $$\frac{ex(n+1,H)}{n+1\choose r}\leq \frac{ex(n,H)}{n\choose r},$$ and finish the proof. But why is the above equality holds? or is this a wrong claim?

1

There are 1 best solutions below

0
On

For simplicity assume that $r=2$, i.e. we are considering graphs. Our goal is to show that $$\frac{\text{ex}(n+1,H)}{\binom{n+1}{2}}\leq \frac{\text{ex}(n,H)}{\binom{n}{2}}.$$

Let $G$ be an $(n+1)$-vertex graph which is $H$-free. For any $S\subset V(G): |S|=n$ one can consider the graph $G[S]$ which is also $H$-free. Since $G[S]$ is an $n$-vertex graph, then $$\frac{e(G[S])}{\binom{n}{2}}\leq \frac{\text{ex}(n,H)}{\binom{n}{2}}.$$

One can vary this uniformly over all $S\subset V(G):|S|=n$ and the LHS is gonna be $\frac{e(G)}{\binom{n+1}{2}}$.

Hence $$\frac{e(G)}{\binom{n+1}{2}}\leq \frac{\text{ex}(n,H)}{\binom{n}{2}}.$$

Since $G$ was $(n+1)$-vertex graph which is $H$-free it implies that $$\frac{\text{ex}(n+1,H)}{\binom{n+1}{2}}\leq \frac{\text{ex}(n,H)}{\binom{n}{2}}.$$

The case of general $r\geq 2$ can be handled in the same way.