1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The equality constraint has rather an algebraic flavour IMHO. For every $S_i\in C_2$ there is $s_i\in\{0,1\}^n$ such that $s_i\cdot s_j$ is $k$ if $i=j$, and is $t$ otherwise. Take $\lambda\in\mathbb R$ such that $t\lambda^2-2k\lambda+n=0$ (there is one iff $k^2\ge tn$). Then $(\lambda s_i-\mathbf1)_{1\le i\le m}$ form an orthonormal basis of $\mathbb R^m$. Moreover, there are infinitely many examples for $|C_2|=n$. Take neughbour sets of vertices in strongly-regular graph. $\endgroup$
    – te4
    Commented Dec 26, 2023 at 17:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .