# Erdos Ko Rado for hypergraphs of bounded degree?

The Erdos-Ko-Rado theorem states that if $H$ is a $k$-uniform hypergraph on $[n]$ which is intersecting, then $|H| \leqslant \binom{n-1}{k-1}$. The easy example which shows this is tight is just take $H$ to be all $k$-subsets containing the element $1$. This example however the degree of the vertex $1$ would be $|H|$. I'm interested if the bound can be improved if we assume bounds on the max degree of $H$, in particular if the max degree is on the order of the average degree. Does anyone know of such a theorem?

A good bound was obtained by Frankl in his paper "Erdos-Ko-Rado theorem with conditions on the maximal degree".

His result is as follows. For $\ell \geq 0$, define the family $$F_\ell = \{ S \in \binom{[n]}{k} : 1 \in S \text{ and } S \cap \{2,\ldots,\ell+1\} \neq \emptyset \} \cup \{ S \in \binom{[n]}{k} : S \supseteq \{2,\ldots,\ell+1\} \}.$$ If $k \leq n/2$ and $F$ is a maximal family whose maximal degree is at most that of $F_\ell$, then $|F| \leq |F_\ell|$.

• Is Frankl's result new enough? Aug 2, 2017 at 15:09
• Not really. It's from 1987. Aug 2, 2017 at 15:19

I returned to this problem after awhile and I can get a slight improvement and show a nice connection between simple graphs and multigraphs. Throughout the following, I will assume that the uniformity, $k$, is fixed and the max degree, $\Delta$ is tending to infinity.

Now, let $g(k,\Delta)$ denote the maximimum number of edges in a simple intersecting $k$-graph with max degree $\Delta$, and let $g^*(k,\Delta)$ denote the equivalent number for multigraphs. In my previous post, I argued three things:

1. $g^*(k-1,\Delta)\leq g(k,\Delta)\leq g^*(k,\Delta)$
2. $g^*(k,\Delta)\leq k\Delta$
3. $g^*(k,\Delta)\geq (k-1+{1\over k})\Delta$ for infinitely many $k$.

I can show an improvement to item 1. when $k$ is fixed and $\Delta\to\infty$ which gives an answer of $g(k,\Delta)\leq (k-1)\Delta+C_k$ where $C_k$ is some (large) constant depending only on $k$.

In fact, I'll show that $g(k,\Delta)\leq g^*(k-1,\Delta)+C_k$. To do so, let $G$ be a simple intersecting $k$-graph with max degree $\Delta$ and set $C_k=k!\cdot k^k$. The value of $C_k$ comes from the Erdos-Rado sunflower lemma. In particular, if $|E(G)|>C_k$, then $G$ contains a sunflower with $k+1$ petals. Since this is the case, we can pull off sunflowers $S_1,\dots,S_\ell$ from $G$, each having $k+1$ petals, where $\ell$ is the smallest integer with $|E(G)|\leq\ell(k+1)+ C_k$..

Now, let $S_i'$ denote the core of $S_i$. Since $G$ was a simple graph, each $S_i'$ has size at most $k-1$. Thus, if $G'$ is the multigraph with edge set $S_i'$, then $G'$ is $\leq(k-1)$-uniform. I claim that $G'$ is actually intersecting as well. Indeed, this follows from the fact that each $S_i$ is a $k$-uniform sunflower with $k+1$ petals, so since $G$ was intersecting, it must be the case that the cores of each of these sunflowers intersect as well.

Finally, if $\Delta'$ is the max degree of $G'$, we have $\Delta'\leq \Delta/(k+1)$ since each core corresponds to $k+1$ edges of $G$. Hence, $\ell=|E(G')|\leq g^*(k-1,\Delta/(k+1))$. It is not difficult to observe that $t\cdot g^*(s,\Delta)\leq g^*(s,t\Delta)$ by stacking multiple copies of a graph on itself, so we finally have $$|E(G)|\leq \ell(k+1)+C_k\leq (k+1)\cdot g^*(k-1,\Delta/(k+1))+C_k\leq g^*(k-1,\Delta)+C_k.$$

Thus, $g(k,\Delta)\leq g^*(k-1,\Delta)+C_k$. This immediately implies that $g(k,\Delta)\leq (k-1)\Delta+C_k$, which is better than the trivial bound of $k\Delta$ for large $\Delta$.

Unfortunately, I do not know any way to improve the trivial bound of $g^*(k,\Delta)\leq k\Delta$.

• So, you can actually take $C_k=k!(k-1)^k$ since you actually just need sunflowers with $k$ petals to make the argument work. But this doesn't really make much difference. Jun 14, 2018 at 14:09

I just asked the same question myself and came across your question. Any chance you found an answer?

After thinking about it for a bit, I have a couple bounds.Let's first note that this question is also interesting if $H$ is allowed to be a multigraph. Further, if I have a $k$-uniform intersecting multigraph $H$, then I can create an intersecting $(k+1)$-uniform intersecting simple graph $H'$ with $|H'|=|H|$ and $\Delta(H')=\Delta(H)$ by simply introducing a dummy vertex'' on each edge in order to separate multiedges. This being the case, I'll consider multigraphs for the remainder of this post.

Let $k\to\infty$ and $k\mid\Delta$. If $H$ is a maximum $k$-uniform intersecting multigraph with $\Delta(H)\leq\Delta$, then $|H|=(1-o(1))k\Delta$.

Firstly, by looking at a single edge and realizing it must intersect every other edge, you get the trivial upper bound of $|H|\leq k(\Delta-1)+1\leq k\Delta$.

Now for a construction to show a lower bound. Let $q$ be a prime power and consider the projective plane of order $q$ as a hypergraph. This is an intersecting $(q+1)$-uniform graph which is $(q+1)$-regular and has $q^2+q+1$ edges. Form the multigraph $H$ by stacking $c$ copies of the projective plane on top of each other (so each edge has multiplicity $c$). As the projective plane was intersecting, so is $H$ and clearly $\Delta(H)=(q+1)c$ and $|H|=(q^2+q+1)c$, so we have $|H|=(q+{1\over q+1})\Delta(H)$. Therefore, if $k$ is one more than a prime power and $k\mid\Delta$, we can find a $k$-uniform intersecting multigraph $H$ with $\Delta(H)=\Delta$ and $|H|=(k-1+{1\over k})\Delta$.

While this implies the above claim for $k\to\infty$, it is quite unclear to me what the right answer should be for fixed $k$. For $k=2$, it is easy to convince yourself that if $\Delta$ is even, then the answer (for the multigraph case) is $|H|={3\over 2}\Delta$ which is realized by stacking $\Delta/2$ copies of the triangle on top of itself. Even for $k=3$, I'm unsure. The above bound and construction shows that ${7\over 3}\Delta\leq|H|\leq 3\Delta$ where the lower bound is realized by stacking $\Delta/3$ copies of the Fano plane. My intuition says that ${7\over 3}\Delta$ should be much closer to the right answer, but I don't know.