5
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

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|$.

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

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jun 14, 2018 at 14:09
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.