On $t$ -intersecting Hypergraphs with Minimum Positive Codegrees

Sam Spiro¹¹1Dept. of Mathematics, UCSD [email protected]. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1650112.

Abstract

For a hypergraph $\mathcal{H}$ , define the minimum positive codegree $\delta_{i}^{+}(\mathcal{H})$ to be the largest integer $k$ such that every $i$ -set which is contained in at least one edge of $\mathcal{H}$ is contained in at least $k$ edges. For $1\leq s\leq k,t$ and $t\leq r$ , we prove that for $n$ -vertex $t$ -intersecting $r$ -graphs $\mathcal{H}$ with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ , the unique hypergraph with the maximum number of edges is the hypergraph $\mathcal{H}$ consisting of every edge which intersects a set of size $2k-2s+t$ in at least $k-s+t$ vertices provided $n$ is sufficiently large. This generalizes work of Balogh, Lemons, and Palmer who proved this for $s=t=1$ , as well as the Erdős-Ko-Rado theorem when $k=s$ .

1 Introduction

We say that a hypergraph $\mathcal{H}$ is an $r$ -graph if every edge $h\in\mathcal{H}$ has size $r$ , and we say that $\mathcal{H}$ is $t$ -intersecting if $|h\cap h^{\prime}|\geq t$ for any distinct $h,h^{\prime}\in\mathcal{H}$ . The central result concerning $t$ -intersecting $r$ -graphs is the famous Erdős-Ko-Rado theorem.

Theorem 1.1 ([4]).

For $t\leq r$ , if $\mathcal{H}$ is an $n$ -vertex $t$ -intersecting $r$ -graph with the maximum number of edges, then there exists a set $T$ of size $t$ such that $\mathcal{H}$ consists of every edge containing $T$ provided $n$ is sufficiently large.

There exist numerous extensions, variants, and applications of the Erdős-Ko-Rado theorem; see for example the book and survey by Frankl and Tokushige [8, 9] and the book by Godsil and Meagher [11]. Motivated by minimum degree variants of the Erdős-Ko-Rado theorem, Balogh, Lemons, and Palmer [3] considered a variant involving minimum positive codegrees.

Definition 1.

Given a hypergraph $\mathcal{H}$ and integer $i$ , we define its minimum positive $i$ -degree $\delta^{+}_{i}(\mathcal{H})$ to be the largest integer $k$ such that if $S$ is a set of $i$ vertices contained in at least one edge, then $S$ is contained in at least $k$ edges. We adopt the convention that $\delta^{+}_{i}(\mathcal{H})=\infty$ if $\mathcal{H}$ has no edges.

To state the main result of [3], we require one more definition.

Definition 2.

We say that an $r$ -graph $\mathcal{H}$ is an $(a,b)$ -kernel system if there exists $X\subseteq V(\mathcal{H})$ with $|X|=a$ such that $h\in\mathcal{H}$ if and only if $|h\cap X|\geq b$ .

For example, $(t,t)$ -kernel systems are exactly the extremal constructions appearing in the Erdős-Ko-Rado theorem. More generally, Ahlswede and Khachatrian [1] showed that every $n$ -vertex $t$ -intersecting $r$ -graph $\mathcal{H}$ with the maximum number of edges is a $(2i+t,i+t)$ -kernel system for some $i$ provided $n>2r-t$ . There are many other contexts where kernel systems appear as extremal constructions for variants of the Erdős-Ko-Rado theorem, especially for problems related to maximum degrees; see for example [6, 7, 14].

It is not hard to show that if $r\geq k-s+t$ , then an $r$ -uniform $(2k-2s+t,k-s+t)$ -kernel system $\mathcal{H}$ is $t$ -intersecting with $\delta_{r-s}^{+}(\mathcal{H})={k\choose s}$ . The main result of Balogh, Lemons, and Palmer [3] shows that when $s=t=1$ , this is the unique $r$ -graph with these properties which has the maximum number of edges.

Theorem 1.2 ([3]).

Let $k\geq 1$ and let $\mathcal{H}$ be an $n$ -vertex 1-intersecting $r$ -graph with $\delta_{r-1}^{+}(\mathcal{H})\geq k$ . If $\mathcal{H}$ has the maximum number of edges amongst hypergraphs with these properties, then $\mathcal{H}$ is a $(2k-1,k)$ -kernel system if $n$ is sufficiently large in terms of $r$ .

The proof of Theorem 1.2 utilized the delta-system method. Using a similar approach together with some new ideas, we extend Theorem 1.2 to $t$ -intersecting $\mathcal{H}$ which have bounded positive minimum $(r-s)$ -degree for essentially all values of $s$ and $t$ .

Theorem 1.3.

Let $k,r,s,t$ be positive integers with $s\leq k,t$ and $t\leq r$ , and let $\mathcal{H}$ be an $n$ -vertex $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . If $\mathcal{H}$ has the maximum number of edges amongst hypergraphs with these properties, then $\mathcal{H}$ is a $(2k-2s+t,k-s+t)$ -kernel system if $n$ is sufficiently large in terms of $r$ .

This theorem shows a surprising phenomenon: despite only demanding $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ in the hypothesis, the extremal constructions of Theorem 1.3 end up having $\delta_{r-s}^{+}(\mathcal{H})={k\choose s}$ , which is a significantly stronger condition if $s>1$ . We note that the hypothesis $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ in Theorem 1.3 is best possible, since if we only demanded $\delta_{r-s}^{+}(\mathcal{H})\geq{k-1\choose s}$ , then a $(2k-2-2s+t,k-1-s+t)$ -kernel system would satisfy the hypothesis and have significantly more edges.

Let us briefly discuss the range of parameters in Theorem 1.3. Observe that ${k-1\choose s}=0$ for all $k\leq s$ , so there is no loss in generality by considering $k\geq s$ . If $s>t$ , then the problem is essentially trivial in view of Theorem 1.1. This is because a $(t,t)$ -kernel system will satisfy the positive minimum positive codegree condition if $n$ is sufficiently large, and $(t,t)$ -kernel systems have the maximum number of edges amongst $t$ -intersecting $r$ -graphs if $n$ is sufficiently large. If one considers $r<t$ , then any $t$ -intersecting $r$ -graph has at most one edge, so the problem becomes trivial. Thus Theorem 1.3 covers all of the non-trivial ranges of parameters that we could consider for this problem.

2 Proof of Theorem 1.3

Our argument starts off nearly identical to that of [3]. We note that Theorem 1.3 implicitly says that if $r<k-s+t$ , then any $\mathcal{H}$ satisfying the hypothesis of Theorem 1.3 is empty (since $(a,b)$ -kernel systems are empty if $r<b$ ). The following confirms this is the case.

Lemma 2.1.

For $1\leq s\leq k,t$ and $t\leq r$ , if $\mathcal{H}$ is a non-empty $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ , then $r\geq k-s+t$ .

Here and throughout the text we refer to sets $I$ of size $i$ as $i$ -sets.

Proof.

The result is immediate if $k=s$ , so assume $k>s$ . Assume for contradiction that $r\leq k-s+t-1$ and let $h\in\mathcal{H}$ . Because $k>s$ , the minimum positive codegree condition implies that there is another edge $h^{\prime}\neq h$ in $\mathcal{H}$ , and we will choose such an edge so that $|h\cap h^{\prime}|$ is as small as possible.

Observe that $|h\cap h^{\prime}|\geq t\geq s$ since $\mathcal{H}$ is $t$ -intersecting. Let $S\subseteq h\cap h^{\prime}$ be any $s$ -set. By the minimum positive codegree condition, the $(r-s)$ -set $h^{\prime}\setminus S$ is contained in more than ${k-1\choose s}\geq{r-t+s\choose s}$ edges. As $h\setminus(h^{\prime}\setminus S)$ has size at most $r-t+s$ , we conclude that there exist some $s$ -set $S^{\prime}\not\subseteq h\setminus(h^{\prime}\setminus S)$ such that $h^{\prime\prime}:=(h^{\prime}\setminus S)\cup S^{\prime}\in\mathcal{H}$ . Observe that $|h\cap h^{\prime\prime}|<|h\cap h^{\prime}|$ since $h^{\prime\prime}$ was obtained from $h^{\prime}$ be deleting an $s$ -subset of $h$ and adding an $s$ -set that was not contained entirely in $h$ . This contradicts us choosing $|h\cap h^{\prime}|$ as small as possible, a contradiction. ∎

The remainder of our proof relies heavily on sunflowers.

Definition 3.

We say that a hypergraph $\mathcal{F}$ is a sunflower if there exists a set $X$ such that $h\cap h^{\prime}=X$ for any distinct $h,h^{\prime}\in\mathcal{S}$ . In this case we say that $X$ is the core of $\mathcal{F}$ and that the sets $h\setminus X$ with $h\in\mathcal{F}$ are the petals of $\mathcal{F}$ . When $\mathcal{F}$ consists of a single edge $h$ , we adopt the convention that $h$ is the core of $\mathcal{F}$ .

The main result in the theory of sunflowers is the following result of Erdős and Rado.

Theorem 2.2 ([5]).

For every $r,p\geq 1$ , there exists a constant $f(r,p)\leq r!(p-1)^{r}$ such that if $\mathcal{H}$ is an $r$ -graph with more than $f(r,p)$ edges, then $\mathcal{H}$ contains a sunflower with at least $p$ petals.

Much stronger bounds for $f(r,p)$ have been obtained in breakthrough work of Alweiss et. al. [2], but for our purposes we only need that $f(r,p)$ is a constant. Theorem 2.2 does not give any control over the size of the core of a sunflower in $\mathcal{H}$ , and for this we use a result of Mubayi and Zhao [15] which is based off of work of Füredi [10].

Proposition 2.3 ([15]).

If $r>k-s+t$ and $p\geq 1$ , then there exists a constant $C$ depending on $r,p$ such that if $|\mathcal{H}|\geq Cn^{r-k+s-t-1}$ , then $\mathcal{H}$ contains a sunflower with at least $p$ petals and core of size at most $k-s+t$ .

Proposition 2.3 allows us to find sunflowers which have many petals and small cores. The next lemma shows that cores of sunflowers with many petals can not be too small.

Lemma 2.4.

For $1\leq s\leq k,t$ , let $\mathcal{H}$ be a $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . If $\mathcal{F}$ is a sunflower of $\mathcal{H}$ with at least $r+1$ petals and core $Y$ , then $|Y|\geq k-s+t$ .

Proof.

We first observe that every edge $h\in\mathcal{H}$ intersects $Y$ in at least $t$ vertices. Indeed, because $\mathcal{F}$ has at least $r+1$ petals, there exists some petal $P$ of $\mathcal{F}$ which is disjoint from $h$ , and having $h$ and $P\cup Y$ as edges in $\mathcal{H}$ implies that $|h\cap Y|\geq t$ .

Assume for contradiction that $|Y|<k-s+t$ , and let $Z$ be a smallest set of vertices with the property that $|h\cap Z|\geq t$ for all $h\in H$ . Observe that $|Z|\leq|Y|<k-s+t$ since $Y$ is a set with this property. By the minimality of $|Z|$ , there exists some $h\in\mathcal{H}$ which intersects $Z$ in exactly $t$ vertices $\{z_{1},\ldots,z_{t}\}$ . Note that $h\setminus\{z_{1},\ldots,z_{s}\}$ is an $(r-s)$ -set contained in an edge. Moreover, since every edge $h^{\prime}$ intersects $Z$ in at least $t$ vertices, every edge $h^{\prime}$ containing this $(r-s)$ -set must be of the form $(h\setminus\{z_{1},\ldots,z_{s}\})\cup S$ with $S$ an $s$ -subset of $Z\setminus\{z_{s+1},\ldots,z_{t}\}$ since we have $\{z_{s+1},\ldots,z_{t}\}\subseteq h\setminus\{z_{1},\ldots,z_{s}\}$ . The number of choices of such $s$ -sets is exactly ${|Z|-t+s\choose s}\leq{k-1\choose s}$ , a contradiction to this $(r-s)$ -set being contained in more than ${k-1\choose s}$ edges. We conclude the result. ∎

At this point in the analogous proof of [3] for $s=t=1$ with²²2There is a small error in [3] where it is claimed that their argument works for $r\geq k$ as opposed to just $r>k$ . However, a simple modification of their argument gives a correct proof for the $r=k$ case. $r>k$ , it is argued that if $|\mathcal{H}|\gg n^{r-k-1}$ , then $\mathcal{H}$ contains a set $Y\cup Z$ of size $2k-1$ such that every $k$ -subset of $Y\cup Z$ is the core of a sunflower with at least $r+1$ petals. From this observation one can quickly deduce that every edge intersects $Y\cup Z$ in at least $k$ vertices, which implies Theorem 1.2.

Essentially this same argument will work in our general setting if one assumes the stronger hypothesis $\delta_{r-s}^{+}(\mathcal{H})\geq{k\choose s}$ , but it fails when considering the weaker hypothesis $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . For example, if $s=t=2$ and $k=4$ , then one can consider the $r$ -graph $\mathcal{H}$ which consists of every edge containing at least 4 vertices of $\{1,2,3,4,5,6\}$ except for the edges which contain $\{1,2,3,4\}$ . This construction has many edges and satisfies $\delta_{r-2}^{+}(\mathcal{H})=5>{k-1\choose s}$ , but it is not the case that there is a set of size $2k-2s+t$ such that every $(k-s+t)$ -subset is the core of a sunflower with many edges. Thus from this point onwards we will have to deviate significantly from the approach of [3]. The key definition we need is the following.

Definition 4.

Given integers $k,s,t$ and a hypergraph $\mathcal{H}$ , we say that a triple of vertex sets $(h,Y,Z)$ is a bad triple if the following conditions hold:

(1)

The set $h$ is an edge of $\mathcal{H}$ with $|h\cap(Y\cup Z)|<k-s+t$ .
(2)

We have $|Y|=|Z|=k-s+t$ and $|Y\cup Z|=2k-2s+t$ (or equivalently, $|Y\cap Z|=t$ ).
(3)

The sets $Y,Z$ are cores of sunflowers $\mathcal{F}_{Y},\mathcal{F}_{Z}$ . Moreover, every petal $P$ of $\mathcal{F}_{Y}$ is disjoint from every edge of $\mathcal{F}_{Z}$ , and every petal $Q$ of $\mathcal{F}_{Z}$ is disjoint from every edge of $\mathcal{F}_{Y}$ .
(4)

For every edge $h^{\prime}\in\mathcal{H}$ there exist a petal $P$ of $\mathcal{F}_{Y}$ and a petal $Q$ of $\mathcal{F}_{Z}$ such that $h^{\prime}\cap P=h^{\prime}\cap Q=\emptyset$ .
(5)

For any petal $P$ of $\mathcal{F}_{Y}$ , define

$I(P)=\{Y^{\prime}:Y^{\prime}\subseteq(Y\cup Z),\ P\cup Y^{\prime}\in\mathcal{H}\}.$

We have $I(P)=I(P^{\prime})$ for all petals $P,P^{\prime}$ of $\mathcal{F}_{Y}$ .

We note that if $r=k-s+t$ , then all of the conditions except (1) are satisfied if there exist two edges $Y,Z$ with $|Y\cap Z|=t$ (since one can take $\mathcal{F}_{Y},\mathcal{F}_{Z}$ to be sunflowers with 1 edge and the empty set as a petal). If $r>k-s+t$ , then (4) will be satisfied provided $\mathcal{F}_{Y},\mathcal{F}_{Z}$ each have at least $r+1$ edges.

Condition (5) will mostly be used as a technical convenience as follows: if there exists an edge $P\cup Y^{\prime}$ with $P$ a petal of $\mathcal{F}_{Y}$ and $Y^{\prime}\subseteq Y\cup Z$ a set of size $k-s+t$ , then (5) guarantees that $P^{\prime}\cup Y^{\prime}$ will be an edge for any petal $P^{\prime}$ of $\mathcal{F}_{Y}$ . We also note that (5) is the only condition which is asymmetric in $Y$ and $Z$ .

The following two results show that bad triples are the only obstruction to proving Theorem 1.3.

Lemma 2.5.

For $1\leq s\leq t,k$ and $r=k-s+t$ , let $\mathcal{H}$ be an $n$ -vertex $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . If $\mathcal{H}$ contains no bad triples, then $\mathcal{H}$ is a subset of a $(2k-2s+t,k-s+t)$ -kernel system.

Proof.

The result is trivial if $\mathcal{H}$ is empty, so assume $\mathcal{H}$ contains at least one edge. Let $Y,Z$ be (possibly non-distinct) edges of $\mathcal{H}$ such that $|Y\cap Z|$ is as small as possible. We claim that $|Y\cap Z|=t$ . Indeed, we must have $|Y\cap Z|\geq t$ since $\mathcal{H}$ is $t$ -intersecting, so assume for contradiction that $|Y\cap Z|\geq t+1$ . Let $S_{Z}\subseteq Y\cap Z$ be an $s$ -set. Because

|Y\setminus(Z\setminus S_{Z})|\leq k-s+t-(t+1-s)=k-1,

the positive minimum codegree condition implies there is an $s$ -set $\tilde{S}$ such that $\tilde{Z}:=(Z\setminus S_{Z})\cup\tilde{S}$ is an edge with $\tilde{S}\not\subseteq Y\setminus(Z\setminus S_{Z})$ , and in particular $\tilde{S}\not\subseteq Y$ since $\tilde{S}$ is disjoint from $Z\setminus S_{Z}$ . Note that $|Y\cap\tilde{Z}|<|Y\cap Z|$ since $\tilde{Z}$ was formed from $Z$ by deleting an $s$ -set $S_{Z}\subseteq Y$ and adding an $s$ -set $\tilde{S}\not\subseteq Y$ . This contradicts us choosing $Z$ to minimize $|Y\cap Z|$ , so we conclude that $|Y\cap Z|=t$ .

As noted before the lemma, if there existed an edge $h$ with $|h\cap(Y\cup Z)|<k-s+t$ , then $(h,Y,Z)$ would be a bad triple. Thus no such edge exists by hypothesis. We conclude that $\mathcal{H}$ is a subset of a $(2k-2s+t,k-s+t)$ -kernel system, namely the one consisting of every edge which intersects $Y\cup Z$ in at least $k-s+t$ vertices. ∎

Proposition 2.6.

For $1\leq s\leq t,k$ and $r>k-s+t$ , let $\mathcal{H}$ be an $n$ -vertex $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . There exists a constant $C=C(r)$ such that if $|\mathcal{H}|\geq Cn^{r-k+s-t-1}$ and $\mathcal{H}$ contains no bad triples, then $\mathcal{H}$ is a subset of a $(2k-2s+t,k-s+t)$ -kernel system.

Proof.

Let $\mathcal{H}$ be as in the proposition. By Proposition 2.3 and Lemma 2.4, we can guarantee, provided $C$ is sufficiently large in terms of $r$ , that $\mathcal{H}$ contains a sunflower $\mathcal{F}_{Y}^{\prime}$ with core $Y=\{y_{1},\ldots,y_{k-s+t}\}$ and at least

p=(2r+1)f(s,r+1)^{k-s+t}+(r+1)2^{2^{2k-2s+t}}+r(r+1)

petals, where $f(s,r+1)$ is as in Theorem 2.2. Analogous to the proof of Lemma 2.5, we wish to show the following.

Claim 2.7.

There is a set of vertices $Z=\{z_{1},\ldots,z_{k-s+t}\}$ such that $|Y\cap Z|=t$ and such that $Z$ is the core of a sunflower $\mathcal{F}_{Z}^{\prime}$ with at least $2r+1$ petals.

Proof.

For all $i\geq 0$ , define $g(i)=(2r+1)f(s,r+1)^{i}$ . We say that a $(k-s+t)$ -set $Z$ is good if there is a sunflower $\mathcal{F}_{Z}^{\prime}$ with core $Z$ and at least $g(|Y\cap Z|)$ petals. Note that there exists a good set, namely $Y$ . Let $Z$ be a good set such that $|Y\cap Z|$ is as small as possible. We claim that $|Y\cap Z|=t$ , from which the claim will follow since $Z$ is contained in at least $g(t)\geq g(0)=2r+1$ petals.

We first observe that $|Y\cap Z|\geq t$ . Indeed if this was not the case, then since $Z$ is the core of a sunflower with at least $g(0)\geq r+1$ petals, one of these petals $Q$ must be disjoint from $Y$ . Similarly one can find a petal $P$ of $\mathcal{F}_{Y}^{\prime}$ which is disjoint from $Q\cup Z$ , which means the edges $Q\cup Z$ and $P\cup Y$ intersect in less than $t$ vertices, a contradiction.

Assume for contradiction that $|Y\cap Z|\geq t+1$ . Fix an $s$ -set $S_{Z}\subseteq Y\cap Z$ and observe

|Y\setminus(Z\setminus S_{Z})|\leq(k-s+t)-(t+1-s)=k-1.

This implies that for each petal $Q$ of $\mathcal{F}_{Z}^{\prime}$ , there exists some $s$ -set $\tilde{S}_{Q}$ such that $\tilde{S}_{Q}\not\subseteq Y$ and $Q\cup(Z\setminus S_{Z})\cup\tilde{S}_{Q}\in\mathcal{H}$ , as otherwise the $(r-s)$ -set $Q\cup(Z\setminus S_{Z})$ would be contained in at most ${k-1\choose s}$ edges.

Consider the $s$ -graph $\mathcal{S}$ with edge set $\{\tilde{S}_{Q}:Q\textrm{ a petal of }\mathcal{F}_{Z}^{\prime}\}$ . We claim that $\mathcal{S}$ does not contain a sunflower with at least $r+1$ petals. Indeed, assume $\mathcal{S}$ had distinct edges $\tilde{S}_{Q_{1}},\ldots,\tilde{S}_{Q_{r+1}}$ which all have pairwise intersection $W$ . In this case $\mathcal{H}$ would contain a sunflower $\mathcal{F}$ with edges $Q_{i}\cup(Z\setminus S_{Z})\cup\tilde{S}_{Q_{i}}$ and core $(Z\setminus S_{Z})\cup W$ . Note that $|W|<s$ since it is the core of an $s$ -uniform sunflower with more than one edge, so $\mathcal{F}$ is a sunflower in $\mathcal{H}$ with at least $r+1$ petals and a core of size less than $k-s+t$ , a contradiction to Lemma 2.4.

With this we have $|\mathcal{S}|\leq f(s,r+1)$ , and hence there exists some $\tilde{S}\in\mathcal{S}$ such that $\tilde{S}_{Q}=\tilde{S}$ for at least $g(|Y\cap Z|)/f(s,r+1)=g(|Y\cap Z|-1)$ petals $Q$ of $\mathcal{F}_{Z}^{\prime}$ . Thus the set $\tilde{Z}:=(S\setminus S_{Z})\cup\tilde{S}$ is the core of a sunflower with at least $g(|Y\cap\tilde{Z}|-1)$ petals. Note that $|Y\cap\tilde{Z}|<|Y\cap Z|$ because $S_{Z}\subseteq Y$ and $\tilde{S}\subsetneq Y$ by definition of $\tilde{S}_{Q}$ , a contradiction to us choosing $Z$ to be good with $|Y\cap Z|$ as small as possible. In total this implies $|Y\cap Z|\leq t$ , completing the proof. ∎

With $Z$ as in the claim, there are at least $r+1$ petals $Q_{1},\ldots,Q_{r+1}$ which are disjoint from $Y$ , and we let $\mathcal{F}_{Z}$ denote the sunflower with these petals. Amongst the petals of $\mathcal{F}_{Y}^{\prime}$ , there are at least $(r+1)2^{2^{2k-2s+t}}$ petals which are disjoint from every edge of $\mathcal{F}_{Z}$ , and amongst these petals there must exist at least $r+1$ petals $P_{1},\ldots,P_{r+1}$ such that $I(P_{i})=I(P_{j})$ for all $i,j$ (since there are at most $2^{2^{2k-2s+t}}$ possible sets that $I(P)$ could be). Let $\mathcal{F}_{Y}$ be the sunflower with core $Y$ using these $r+1$ petals. We must have $|h\cap(Y\cup Z)|\geq k-s+t$ for all $h\in\mathcal{H}$ , as otherwise $(h,Y,Z)$ would be a bad triple. This means $\mathcal{H}$ is a subset of a $(2k-2s+t,k-s+t)$ -kernel system, namely the one consisting of every edge which intersects $Y\cup Z$ in at least $k-s+t$ vertices. ∎

It remains to argue that hypergraphs as in Theorem 1.3 do not have bad triples.

Lemma 2.8.

For $1\leq s\leq k,t$ , let $\mathcal{H}$ be a $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . If $\mathcal{H}$ has a bad triple $(h,Y,Z)$ with $|h\cap Z|=t$ , then $|h\cap Y\cap Z|<s$ .

Proof.

Assume for contradiction that there exists a bad triple $(h,Y,Z)$ as in the lemma statement and an $s$ -set $S\subseteq h\cap Y\cap Z$ . Let $Q$ be a petal of $\mathcal{F}_{Z}$ which is disjoint from $h$ , and consider the $(r-s)$ -set $Q\cup(Z\setminus S)$ . Observe that if $h^{\prime}=Q\cup(Z\setminus S)\cup S^{\prime}$ is an edge containing this $(r-s)$ -set and $P$ is a petal of $\mathcal{F}_{Y}$ disjoint from $h^{\prime}$ , then

|h^{\prime}\cap(P\cup Y)|=|(Z\setminus S)\cap Y|+|S^{\prime}\cap Y|=t-s+|S^{\prime}\cap Y|,

so we must have $|S^{\prime}\cap Y|=s$ , which implies $S^{\prime}\subseteq Y\setminus(Z\setminus S):=Y^{\prime}$ since $S^{\prime}$ must be disjoint from $Z\setminus S$ . As there are more than ${k-1\choose s}$ edges containing $Q\cup(Z\setminus S)$ , and since $|Y^{\prime}|=k-s+t-(t-s)=k$ , we conclude that for every $y\in Y^{\prime}$ there exists an edge $h_{y}$ containing $y$ and $Q\cup(Z\setminus S)$ . Because $(h,Y,Z)$ is a bad triple, we have $|h\cap(Y\cup Z)|<k-s+t=|Y|$ , and hence there exists some $y\in Y\setminus h$ . With this we have $|h\cap h_{y}|\leq t-1$ because $|h\cap(Q\cup Z)|=t$ and we construct $h_{y}$ by deleting from $Q\cup Z$ an $s$ -set $S\subseteq h\cap Z$ and then adding an $s$ -set using some $y\notin h$ . This contradicts $\mathcal{H}$ being $t$ -intersecting, giving the result. ∎

Lemma 2.9.

For $1\leq s\leq k,t$ , let $\mathcal{H}$ be a $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ . If $\mathcal{H}$ has a bad triple, then it has a bad triple of the form $(h,Y,Z)$ with $|h\cap Z|=t$ and $|h\cap Y\cap Z|\geq t-s+1$ .

Proof.

Let $(h,Y,Z)$ be a bad triple with $|h\cap Z|$ as small as possible, and assume for contradiction that $|h\cap Z|\geq t+1$ . Let $S\subseteq h\cap Z$ be an arbitrary set of $s$ vertices. Observe that if $h^{\prime}$ is an edge containing $h\setminus S$ and $S^{\prime}:=h^{\prime}\setminus(h\setminus S)$ , then $S^{\prime}\subseteq Z\setminus(h\setminus S)$ , as otherwise $(h^{\prime},Y,Z)$ would be a bad triple with $|h^{\prime}\cap Z|<|h\cap Z|$ , contradicting the minimality of $(h,Y,Z)$ . We have $|Z\setminus(h\setminus S)|\leq(k-s+t)-(t+1-s)=k-1$ , so there are at most ${k-1\choose s}$ edges containing $h\setminus S$ , a contradiction to the minimum positive codegree condition. We conclude that $|h\cap Z|\leq t$ , and we must have $|h\cap Z|\geq t$ since $\mathcal{H}$ is $t$ -intersecting and $\mathcal{F}_{Z}$ contains a petal which is disjoint from $h$ . We conclude that $|h\cap Z|=t$ .

Now consider $(h,Y,Z)$ a bad triple with $|h\cap Z|=t$ and with $|h\cap Y\cap Z|$ as large as possible. Asume for contradiction that $|h\cap Y\cap Z|\leq t-s$ , which implies there exists an $s$ -set $S\subseteq(Y\cap Z)\setminus h$ and also some $z\in(Z\cap h)\setminus Y$ . Let $P$ be a petal of $\mathcal{F}_{Y}$ , and observe that the $(r-s)$ -set $P\cup(Y\setminus S)$ intersects any edge $Q\cup Z$ with $Q$ a petal of $\mathcal{F}_{Z}$ in $t-s$ vertices. Thus any edge containing $P\cup(Y\setminus S)$ must also contain an $s$ -set from the set $Z\setminus(Y\setminus S)$ . As $|Z\setminus(Y\setminus S)|=k$ , and since the $(r-s)$ -set is in more than ${k-1\choose s}$ edges, there must exist a set $S^{\prime}\subseteq Z\setminus(Y\setminus S)$ such that $P\cup(Y\setminus S)\cup S^{\prime}$ is an edge with $z\in S^{\prime}$ . Define $Y^{\prime}=(Y\setminus S)\cup S^{\prime}$ , noting that $|Y^{\prime}\cap Z|=t$ . Observe that $|h\cap Y^{\prime}\cap Z|>|h\cap Y\cap Z|$ , since we formed $Y^{\prime}$ by deleting from $Y$ an $s$ -set which is disjoint from $h$ and then added an $s$ -set containing a vertex in $Z\cap h$ . Also observe that due to condition (5) for bad triples, $Y^{\prime}$ is the core of a sunflower whose petals are the same as $\mathcal{F}_{Y}$ (i.e. since $P\cup Y^{\prime}$ is an edge and $Y^{\prime}\subseteq Y\cup Z$ , we have that $P^{\prime}\cup Y^{\prime}$ is an edge for every petal $P^{\prime}$ of $\mathcal{F}_{Y}$ ). Further, $Y^{\prime}\cup Z=Y\cup Z$ , so (5) continues to hold and we conclude that $(h,Y^{\prime},Z)$ is a bad triple with $|h\cap Z|=t$ and $|h\cap Y^{\prime}\cap Z|>|h\cap Y\cap Z|$ , a contradiction to our choice of triple. ∎

Note that these two lemmas immediately show that there are no bad triples if $t\geq 2s-1$ , but we will need to work harder to get the result for all $t$ . The last tool we need is a particular case of the Kruskal-Katona theorem.

Lemma 2.10 ([12, 13]).

For an $s$ -graph $\mathcal{S}$ and $0\leq i\leq s$ , let $\partial^{i}\mathcal{S}$ be the $i$ -graph with edge set $\{S^{\prime}:S^{\prime}\subseteq S\in\mathcal{H},\ |S^{\prime}|=i\}$ . If $|\mathcal{S}|={k-1\choose s}$ , then $|\partial^{i}\mathcal{S}|\geq{k-1\choose i}$ .

With this we can prove that bad triples do not exist.

Proposition 2.11.

For $1\leq s\leq k,t$ , if $\mathcal{H}$ is a $t$ -intersecting $r$ -graph with $\delta_{r-s}^{+}(\mathcal{H})>{k-1\choose s}$ , then $\mathcal{H}$ does not contain a bad triple.

Proof.

Assume for contradiction that $\mathcal{H}$ contains a bad triple, so by Lemma 2.9 there exists a bad triple $(h,Y,Z)$ with $|h\cap Z|=t$ and $|h\cap Y\cap Z|\geq t-s+1$ . Let $T\subseteq h\cap Y\cap Z$ be a set of $t-s$ vertices, and let $S_{h}=(h\cap Z)\setminus T$ and $S_{Y}=(Y\cap Z)\setminus T$ . Note that $S_{h},S_{Y}$ are $s$ -sets since $h,Y$ both intersect $Z$ in exactly $t$ vertices.

Claim 2.12.

Let $P$ be a petal of $\mathcal{F}_{Y}$ which is disjoint from $h$ . Define

\mathcal{S}_{h}=\{S:|S|=s,\ (h\setminus S_{h})\cup S\in\mathcal{H}\},\hskip 10.00002pt\mathcal{S}_{Y}=\{S:|S|=s,\ P\cup(Y\setminus S_{Y})\cup S\in\mathcal{H}\}.

The set systems $\mathcal{S}_{h},\mathcal{S}_{Y}$ have the following properties:

(a)

We have $|\mathcal{S}_{h}|,|\mathcal{S}_{Y}|>{k-1\choose s}$ ,
(b)

Every $S\in\mathcal{S}_{h}\cup\mathcal{S}_{Y}$ is an $s$ -set which is a subset of the $k$ -set $Z\setminus T$ ,
(c)

The sets $\mathcal{S}_{h},\mathcal{S}_{Y}$ are disjoint, and
(d)

Every $S^{\prime}_{h}\in\mathcal{S}_{h}$ and $S^{\prime}_{Y}\in\mathcal{S}_{Y}$ satisfy $|S^{\prime}_{h}\cap S^{\prime}_{Y}|\geq 2s+1-k$ .

Proof.

Property (a) follows immediately since the $(r-s)$ -sets $h\setminus S_{h}$ and $P\cup(Y\setminus S_{Y})$ are contained in an edge. For (b), every element of $\mathcal{S}_{h}\cup\mathcal{S}_{Y}$ is an $s$ -set by definition. Note that the $(r-s)$ -set $h\setminus S_{h}$ intersects $Z$ in $t-s$ vertices. If $S$ is such that $(h\setminus S_{h})\cup S$ is an edge, then one can choose a petal $Q$ of $\mathcal{F}_{Z}$ which is disjoint from $(h\setminus S_{h})\cup S$ , which means

|((h\setminus S_{h})\cup S)\cap(Q\cup Z)|=t-s+|S\cap Z|.

This implies that we must have $|S\cap Z|\geq s$ , i.e. $S\subseteq Z$ . Moreover we have $S\subseteq Z\setminus T$ since $S$ must be disjoint from $(h\setminus S_{h})\supseteq T$ . An identical argument holds for $\mathcal{S}_{Y}$ , proving (b).

For (c), assume for contradiction that there existed $S\in\mathcal{S}_{h}\cap\mathcal{S}_{Y}$ . Let $h^{\prime}=(h\setminus S_{h})\cup S$ and $Y^{\prime}:=(Y\setminus S_{Y})\cup S$ . Because $P\cup Y^{\prime}$ is an edge, condition (5) for bad triples implies $Y^{\prime}\subseteq Y\cup Z$ is the core of a sunflower using the same petals as $\mathcal{F}_{Y}$ . Thus $(h^{\prime},Y^{\prime},Z)$ is a bad triple with $|h^{\prime}\cap Z|=t$ and $|h^{\prime}\cap Y^{\prime}\cap Z|\geq|S|=s$ , a contradiction to Lemma 2.8.

For (d), using $S_{h},S_{Y}\subseteq Z$ together with $|h\cap Z|=t$ and $|h\cap(Y\cup Z)|\leq k-s+t-1$ implies

|((h\setminus S_{h})\cap(Y\setminus S_{Y}))\setminus Z|=|(h\cap Y)\setminus Z|\leq k-s-1.

We also have $|(h\setminus S_{h})\cap(Y\setminus S_{Y})\cap Z|=|T|=t-s$ , so in total

|(h\setminus S_{h})\cap(Y\setminus S_{Y})|\leq k+t-2s-1.

Observe that if $S_{h}^{\prime}\in\mathcal{S}_{h}$ , then $S_{h}^{\prime}$ is disjoint from $P\cup(Y\setminus S_{Y})$ since $S_{h}^{\prime}\subseteq Z\setminus T$ . Similarly every $S_{Y}^{\prime}\in\mathcal{S}_{Y}$ is disjoint from $h\setminus S_{h}$ . Thus if $S_{h}^{\prime}\in\mathcal{S}_{h}$ and $S^{\prime}_{Y}\in\mathcal{S}_{Y}$ , for their corresponding edges to intersect in at least $t$ vertices we must have $|S^{\prime}_{h}\cap S^{\prime}_{Y}|\geq t-(k+t-2s-1)=2s+1-k$ , proving the result. ∎

It remains to show that it is impossible to construct set systems $\mathcal{S}_{h},\mathcal{S}_{Y}$ with the properties as in this claim. Observe that properties (b), (c), (a) imply that

{k\choose s}\geq|\mathcal{S}_{h}\cup\mathcal{S}_{Y}|=|\mathcal{S}_{h}|+|\mathcal{S}_{Y}|\geq 2+2{k-1\choose s}.

Note that this inequality is equivalent to ${k-1\choose s-1}\geq 2+{k-1\choose s}$ , which is false for $k\geq 2s$ . Thus from now on we may assume $k\leq 2s-1$ , which in particular means (d) is a non-trivial condition.

Observe that $s\leq k\leq 2s-1$ implies $0\leq k-s\leq s-1$ , so $\partial^{k-s}\mathcal{S}_{h}$ is well defined. Let $\mathcal{S}^{\prime}$ be the $s$ -graph with edge set $\{(Z\setminus T)\setminus S:S\in\partial^{k-s}\mathcal{S}_{h}\}$ . That is, $\mathcal{S}^{\prime}$ is the “complement” of $\partial^{k-s}\mathcal{S}_{h}$ in $Z\setminus T$ . For every $S^{\prime}\in\mathcal{S}^{\prime}$ , there exists some $S\in\mathcal{S}_{h}$ such that $|S\cap S^{\prime}|=2s-k$ ; namely, this holds whenever $S^{\prime}$ is the complement of a $(k-s)$ -subset of $S$ . By (d), it must be that $\mathcal{S}^{\prime}$ and $\mathcal{S}_{Y}$ are disjoint $s$ -graphs on $Z\setminus T$ . Using this together with (a), $|\mathcal{S}^{\prime}|=|\partial^{k-s}\mathcal{S}_{h}|$ , and Lemma 2.10 gives

{k\choose s}\geq|\mathcal{S}_{Y}\cup\mathcal{S}^{\prime}|=|\mathcal{S}_{Y}|+|\mathcal{S}^{\prime}|>{k-1\choose s}+{k-1\choose k-s}={k-1\choose s}+{k-1\choose s-1}={k\choose s}.

This is a contradiction, proving the result. ∎

Proof of Theorem 1.3.

Let $\mathcal{H}$ be a hypergraph satisfying the hypothesis of the theorem with the maximum number of edges, and observe that $\mathcal{H}$ has no bad triples by Proposition 2.11. If $r<k-s+t$ , then $\mathcal{H}$ is empty by Lemma 2.1. If $r=k-s+t$ , then $\mathcal{H}$ is contained in a $(2k-2s+t,k-s+t)$ -kernel system by Lemma 2.5, and since $\mathcal{H}$ has the maximum number of edges it must in fact be such a kernel system. Thus we may assume $r>k-s+t$ .

Because $(2k-2s+t,k-s+t)$ -kernel systems satisfy the hypothesis of the theorem and have $\Omega(n^{r-k+s-t})$ edges, we must have $|\mathcal{H}|=\Omega(n^{r-k+s-t})$ as well. Proposition 2.6 implies $\mathcal{H}$ is contained in a $(2k-2s+t,k-s+t)$ -kernel system if $n$ is sufficiently large, and because $\mathcal{H}$ has the maximum number of edges, it must be such a kernel system, proving the result. ∎

Our proof in fact gives a stability result: if $\mathcal{H}$ is as in Theorem 1.3 with $|\mathcal{H}|\gg n^{r-k+s-t-1}$ , then $\mathcal{H}$ is a subset of a $(2k-2s+t,k-s+t)$ -kernel system. In the special case of $r=k-s+t$ , this conclusion holds regardless of the size of $\mathcal{H}$ .

We made no attempt at optimizing how large $n$ must be for Theorem 1.3 to hold. A careful analysis shows that our argument works provided $n\approx r^{rs(k-s+t)}+2^{r2^{2k-2s+t}}$ due to demanding a sunflower with sufficiently many petals to find a sunflower on $Z$ , as well as to utilize condition (5) for bad triples. It is not too difficult to provide an alternative proof by replacing (5) with the condition that if $r>k-s+t$ , then the sunflower $\mathcal{F}_{Y}$ contains at least $(2r)^{k(s+1-|h\cap Y\cap Z|)}$ petals. This ultimately gives a bound that works for $n\approx r^{rs(k-s+t)}$ , which matches the bound of $n\approx r^{rk}$ implicitly proven in [3] when $s=t=1$ . However, this alternative proof is slightly more involved, so we elected to use the current argument at the cost of weaker (implicit) bounds.

As in [3], one may be able to prove that Theorem 1.3 holds for $n\approx r^{s(k-s+t)}$ if $k$ is small, and in particular one may be able to adapt the ideas of [3] to prove such a bound when $k=s+1$ .

Acknowledgments. The author thanks Jason O’Neill for engaging conversations and comments on an earlier draft, and Cory Palmer for clarifying some of the points from [3].

References

[1] R. Ahlswede and L. H. Khachatrian. The complete intersection theorem for systems of finite sets. European Journal of Combinatorics, 18(2):125–136, 1997.
[2] R. Alweiss, S. Lovett, K. Wu, and J. Zhang. Improved bounds for the sunflower lemma. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 624–630, 2020.
[3] J. Balogh, N. Lemons, and C. Palmer. Maximum size intersecting families of bounded minimum positive co-degree. SIAM Journal on Discrete Mathematics, 35(3):1525–1535, 2021.
[4] P. Erdős, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. The Quarterly Journal of Mathematics, 12(1):313–320, 1961.
[5] P. Erdős and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 1(1):85–90, 1960.
[6] P. Frankl. On intersecting families of finite sets. Journal of Combinatorial Theory, Series A, 24(2):146–161, 1978.
[7] P. Frankl. Erdös-Ko-Rado theorem with conditions on the maximal degree. Journal of Combinatorial Theory, Series A, 46(2):252–263, 1987.
[8] P. Frankl and N. Tokushige. Invitation to intersection problems for finite sets. Journal of Combinatorial Theory, Series A, 144:157–211, 2016.
[9] P. Frankl and N. Tokushige. Extremal problems for finite sets, volume 86. American Mathematical Soc., 2018.
[10] Z. Füredi. On finite set-systems whose every intersection is a kernel of a star. Discrete mathematics, 47:129–132, 1983.
[11] C. Godsil and K. Meagher. Erdos-Ko-Rado theorems: algebraic approaches. Number 149. Cambridge University Press, 2016.
[12] G. Katona. A theorem of finite sets. In Classic Papers in Combinatorics, pages 381–401. Springer, 2009.
[13] J. B. Kruskal. The number of simplices in a complex. Mathematical optimization techniques, 10:251–278, 1963.
[14] N. Lemons and C. Palmer. The unbalance of set systems. Graphs and Combinatorics, 24(4):361–365, 2008.
[15] D. Mubayi and Y. Zhao. Forbidding complete hypergraphs as traces. Graphs and Combinatorics, 23(6):667–679, 2007.

On tt-intersecting Hypergraphs with Minimum Positive Codegrees

Abstract

1 Introduction

Theorem 1.1 ([4]).

Definition 1.

Definition 2.

Theorem 1.2 ([3]).

Theorem 1.3.

2 Proof of Theorem 1.3

Lemma 2.1.

Proof.

Definition 3.

Theorem 2.2 ([5]).

Proposition 2.3 ([15]).

Lemma 2.4.

Proof.

Definition 4.

Lemma 2.5.

Proof.

Proposition 2.6.

Proof.

Claim 2.7.

Proof.

Lemma 2.8.

Proof.

Lemma 2.9.

Proof.

Lemma 2.10 ([12, 13]).

Proposition 2.11.

Proof.

Claim 2.12.

Proof.

Proof of Theorem 1.3.

References

On $t$ -intersecting Hypergraphs with Minimum Positive Codegrees