Skip to main content
added 131 characters in body
Source Link
Groups
  • 379
  • 2
  • 10

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.

Let $C_1\subseteq \mathcal{F}$ be such that any two elements in $C_1$ share at least $t$ elements in $[n]$. Then a generalised version of Erdős–Ko–Rado theorem asserts that $|C_1|\leqslant {n-t\choose k-t}$.

This can be interpreted in graph theory. The generalised Kneser graph $K(n,k,t-1)$ is defined to be of vertex set $\mathcal{F}$, with two vertices adjacent if and only if they meet at most $(t-1)$ elements in $[n]$. So the set $C_1$ defined above is an independent set of $K(n,k,t-1)$.

Now let $C_2\subseteq\mathcal{F}$ be such that any two elements in $C_2$ share exactly $t$ elements in $[n]$.

Question. Do we have a known good upper bound on $|C_2|$?

As an obvious corollary of the generalised EKR theorem, we have $|C_2|\leqslant {n-t\choose k-t}$. Indeed, if $t = k-1$, then this bound is best possible. Another bound is given by Frankl and Wilson, butwho show that $|C_2| \leqslant n$. But in general it seems that this bound is, both bounds might not sharpbe best possible. It has been more than 40 years since Frankl and Wilson. Is there any better boundimprovement of the bounds?

Again, it can be interpreted in the graph theory language. The uniform subset graph (see this paper), denoted $G(n,k,t)$, is a graph with vertices $\mathcal{F}$, and two vertices are joined by an edge if and only if they share exactly $t$ elements in $[n]$. Thus, $C_2$ is a clique of $G(n,k,t)$, and the bound I asked is an upper bound on the clique number of $G(n,k,t)$.

I am not familiar with extremal set theory or graph theory, so apologies if the question is too striaghtforward for experts.

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.

Let $C_1\subseteq \mathcal{F}$ be such that any two elements in $C_1$ share at least $t$ elements in $[n]$. Then a generalised version of Erdős–Ko–Rado theorem asserts that $|C_1|\leqslant {n-t\choose k-t}$.

This can be interpreted in graph theory. The generalised Kneser graph $K(n,k,t-1)$ is defined to be of vertex set $\mathcal{F}$, with two vertices adjacent if and only if they meet at most $(t-1)$ elements in $[n]$. So the set $C_1$ defined above is an independent set of $K(n,k,t-1)$.

Now let $C_2\subseteq\mathcal{F}$ be such that any two elements in $C_2$ share exactly $t$ elements in $[n]$.

Question. Do we have a known good upper bound on $|C_2|$?

As an obvious corollary of the generalised EKR theorem, we have $|C_2|\leqslant {n-t\choose k-t}$. Indeed, if $t = k-1$, then this bound is best possible, but in general it seems that this bound is not sharp. Is there any better bound?

Again, it can be interpreted in the graph theory language. The uniform subset graph (see this paper), denoted $G(n,k,t)$, is a graph with vertices $\mathcal{F}$, and two vertices are joined by an edge if and only if they share exactly $t$ elements in $[n]$. Thus, $C_2$ is a clique of $G(n,k,t)$, and the bound I asked is an upper bound on the clique number of $G(n,k,t)$.

I am not familiar with extremal set theory or graph theory, so apologies if the question is too striaghtforward for experts.

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.

Let $C_1\subseteq \mathcal{F}$ be such that any two elements in $C_1$ share at least $t$ elements in $[n]$. Then a generalised version of Erdős–Ko–Rado theorem asserts that $|C_1|\leqslant {n-t\choose k-t}$.

This can be interpreted in graph theory. The generalised Kneser graph $K(n,k,t-1)$ is defined to be of vertex set $\mathcal{F}$, with two vertices adjacent if and only if they meet at most $(t-1)$ elements in $[n]$. So the set $C_1$ defined above is an independent set of $K(n,k,t-1)$.

Now let $C_2\subseteq\mathcal{F}$ be such that any two elements in $C_2$ share exactly $t$ elements in $[n]$.

Question. Do we have a known good upper bound on $|C_2|$?

As an obvious corollary of the generalised EKR theorem, we have $|C_2|\leqslant {n-t\choose k-t}$. Indeed, if $t = k-1$, then this bound is best possible. Another bound is given by Frankl and Wilson, who show that $|C_2| \leqslant n$. But in general, both bounds might not be best possible. It has been more than 40 years since Frankl and Wilson. Is there any improvement of the bounds?

Again, it can be interpreted in the graph theory language. The uniform subset graph (see this paper), denoted $G(n,k,t)$, is a graph with vertices $\mathcal{F}$, and two vertices are joined by an edge if and only if they share exactly $t$ elements in $[n]$. Thus, $C_2$ is a clique of $G(n,k,t)$, and the bound I asked is an upper bound on the clique number of $G(n,k,t)$.

I am not familiar with extremal set theory or graph theory, so apologies if the question is too striaghtforward for experts.

Post Undeleted by Groups
Post Deleted by Groups
Source Link
Groups
  • 379
  • 2
  • 10

On a generalisation of the EKR theorem

Let $n > k >t$ be positive integers, and let us assume $2k \leqslant n$. We denote the set of $k$-subsets of $[n]$ by $\mathcal{F}$.

Let $C_1\subseteq \mathcal{F}$ be such that any two elements in $C_1$ share at least $t$ elements in $[n]$. Then a generalised version of Erdős–Ko–Rado theorem asserts that $|C_1|\leqslant {n-t\choose k-t}$.

This can be interpreted in graph theory. The generalised Kneser graph $K(n,k,t-1)$ is defined to be of vertex set $\mathcal{F}$, with two vertices adjacent if and only if they meet at most $(t-1)$ elements in $[n]$. So the set $C_1$ defined above is an independent set of $K(n,k,t-1)$.

Now let $C_2\subseteq\mathcal{F}$ be such that any two elements in $C_2$ share exactly $t$ elements in $[n]$.

Question. Do we have a known good upper bound on $|C_2|$?

As an obvious corollary of the generalised EKR theorem, we have $|C_2|\leqslant {n-t\choose k-t}$. Indeed, if $t = k-1$, then this bound is best possible, but in general it seems that this bound is not sharp. Is there any better bound?

Again, it can be interpreted in the graph theory language. The uniform subset graph (see this paper), denoted $G(n,k,t)$, is a graph with vertices $\mathcal{F}$, and two vertices are joined by an edge if and only if they share exactly $t$ elements in $[n]$. Thus, $C_2$ is a clique of $G(n,k,t)$, and the bound I asked is an upper bound on the clique number of $G(n,k,t)$.

I am not familiar with extremal set theory or graph theory, so apologies if the question is too striaghtforward for experts.