## On set systems without singleton intersections

## Danila Cherkashin

August 2, 2024

## Abstract

Consider a family F of k -subsets of an ambient ( k 2 -k + 1) -set such that no pair of k -subsets in F intersects in exactly one element. In this short note we show that the maximal size of such F is ( k 2 - -k 1 k -2 ) for every k &gt; 1 .

Keywords: Johnson scheme, Erd˝s-S´s problem, finite projective planes. o o

## 1 Introduction

A large branch of combinatorics grows from the celebrated Erd˝s-Ko-Rado theorem [5], which states that a o family of pairwise intersecting k -element subsets of an n -element set has size at most ( n -1 k -1 ) provided that n ≥ 2 k .

For our aim it is convenient to define a Johnson graph J n, k, t ( ) , whose vertices are k -element subsets of an n -element set and edges connect pairs of vertices with intersection t . An independent set is a vertex subset of a graph such that it does not contain an edge. Let α G ( ) stand for the size of a maximal independent set in a graph G .

In this language the statement of the Erd˝s-Ko-Rado theorem is o

$$\alpha ( J [ n, k, 0 ] ) = \binom { n - 1 } { k - 1 }$$

for n ≥ 2 k . The problem of finding α J n, k, t ( [ ]) is known as Erd˝ os-S´s forbidden intersection problem. o The bibliography on this problem is wide and the proofs use very different techniques. Let us briefly provide the highlights. Frankl and F¨redi [6] used so-called u ∆ -system method to show that α J n, k, t ( [ ]) = ( n -t k -t ) for n &gt; n 0 ( k ) and k ≥ 2 t +2 .

Another very general result was obtained by Frankl and Wilson [7] by a rank bound: it gives α J n, k, t ( [ ]) ≤ ( n k - -t 1 ) for k &gt; 2 t and k -t being a prime power. This result has important applications to discrete geometry, see [10, 16].

Recently, Ellis, Keller and Lifshitz [4, 12] used junta-method to determine α J n, k, t ( [ ]) for ε &lt; k/n &lt; 1 / 2 -ε and n &gt; n 0 ( t, ε ) . Kupavskii and Zakharov showed that α J n, k, t ( [ ]) = ( n - -t 1 k - -t 1 ) for k &gt; k 0 , n = /ceilingleft k α /ceilingright , t = ⌈ k β ⌉ , where α &gt; 1 and 1 / 2 &gt; β &gt; 0 satisfy α &gt; 1 + 2 β . They use spread approximation technique [1]. Also let us mention that α J n, ( [ 4 1]) = , n -2 for n ≥ 9 , see Keevash-Mubayi-Wilson [11].

Our contribution is the following

( 2 )

Theorem 1. For every k &gt; 1 one has

$$\alpha ( J [ k ^ { 2 } - k + 1, k, 1 ] ) = { k ^ { 2 } - k - 1 \choose k - 2 }.$$

Note that for k &gt; k 0 Theorem 1 follows from the mentioned result of Kupavskii and Zakharov [13].

## 2 Tools

## 2.1 Johnson scheme and Bose-Mesner algebra

The facts from this subsection can be found in books [8] and [2].

An associative scheme is a pair ( V, R ) consisting of a finite set V and a family of non-empty binary relations R on V , and satisfying the following properties:

1. sets R ∈ R form a partition V 2 ;

- 2. the diagonal ∆( V ) of the set V 2 is an element of R ;
- 3. the set R is closed under the interchange of the first and second coordinates in V 2 ;
- 4. for arbitrary relations R,S,T ∈ R numbers

$$| v \in V \, \colon ( u, v ) \in R, ( v, w ) \in S |$$

are the same for all ( u, w ) ∈ T .

The classical Johnson scheme is given by

$$V = \binom { [ n ] } { k } ; \ \ R _ { i } \coloneqq \{ ( v, u ) \in V \times V \colon \langle v, u \rangle = k - i \}, \ \ i = 0, \dots k.$$

The Bose-Mesner algebra of the Johnson scheme is the algebra of ( n k ) × ( n k ) matrices, with entries defined by A x, y ( ) := f ( | x ∩ y | ) . Since this is indeed algebra, these matrices are simultaneously diagonalizable. A standard basis of the Bose-Mesner algebra is formed by matrices B x,y i ( ) := ( | x y \ | i ) , i = 0 , . . . , k . The eigenvalues of B i are given by

$$\mu _ { j } ^ { ( i ) } = ( - 1 ) ^ { j } \binom { k - j } { i - j } \binom { n - i - j } { k - j }.$$

Then the machinery offers to represent any matrix A from the Bose-Mesner algebra as ∑ b B i i and get it spectrum as

$$\lambda _ { j } = \sum _ { i = 0 } ^ { k } b _ { i } \mu _ { j } ^ { ( i ) }.$$

Let I be a subset of ( [ n ] k ) and χ I stand for its characteristic vector. Denote by c i , i = 0 , . . . , k the coefficients in the decomposition of χ I with respect to the common eigenspaces of the Bose-Mesner algebra.

## 2.2 Hoffman bound

The following celebrated theorem is widely known as Hoffman ratio bound [9].

Theorem 2. Let A be a pseudoadjacency matrix of a d -regular N -vertex graph G with non-negative entries. Then

$$\alpha ( G ) \leq N \frac { - \lambda _ { m i n } } { d - \lambda _ { m i n } },$$

where α G ( ) is the independence number of G .

The proof is a one-line collection of several simple observations. Let I be any independent set in G and χ I stand for its characteristic vector. Then

$$0 = ( A \chi _ { I }, \chi _ { I } ) = \sum _ { i = 1 } ^ { N } a _ { i } ^ { 2 } \lambda _ { i } \geq a _ { 1 } ^ { 2 } d + ( a _ { 2 } ^ { 2 } + \cdots + a _ { N } ^ { 2 } ) \lambda _ { m i n } = \frac { | I | ^ { 2 } } { N } d + \left ( | I | - \frac { | I | ^ { 2 } } { N } \right ) \lambda _ { m i n },$$

where a i are the coefficients in the decomposition of χ I in the eigenbasis of A . Here we use that a spectral radius of a d -regular graph is d and it is achieved at the all-unit vector. Also in the case of an edge-transitive graph Hoffman bound coincides with Lov´sz theta-bound [15]. a

## 3 The proof

Proof of Theorem 1. An example of an independent set of size ( k 2 - -k 1 k -2 ) is given by a collection of all sets, containing elements 1 and 2.

Let A be the adjacency matrix of the Johnson graph J n, k, ( 1) . Clearly, this matrix is given by f (1) = 1 , f (0) = f (2) = · · · = f ( k ) = 0 . It is straightforward to check that the coefficients in the standard basis of the Bose-Mesner algebra are the following

$$b _ { 0 } = b _ { 1 } = \dots = b _ { k - 2 } = 0, \ \ b _ { k - 1 } = 1, \ \ b _ { k } = - k$$

and

$$\lambda _ { 0 } = - k { n - k \choose k } + k { n - k + 1 \choose k } = k { n - k \choose k - 1 },$$

$$\lambda _ { 1 } = k \binom { n - k - 1 } { k - 1 } - ( k - 1 ) \binom { n - k } { k - 1 }, \ \ \lambda _ { 2 } = - k \binom { n - k - 2 } { k - 2 } + ( k - 2 ) \binom { n - k - 1 } { k - 2 }.$$

For n = k 2 -k +1 we have

$$\lambda _ { 1 } = \lambda _ { 2 } = - \frac { 1 } { k - 1 } \binom { n - k } { k - 1 } < 0$$

and

$$\lambda _ { 3 } = k { n - k - 3 \choose k - 3 } - ( k - 3 ) { n - k - 2 \choose k - 3 } = \frac { 2 k ^ { 2 } - 3 k - 3 } { k ^ { 2 } - 3 k + 2 } { n - k - 3 \choose k - 3 } > 0.$$

Also | λ 4 | , | λ 5 | , . . . , | λ k | ≤ k ( n -k k -3 ) , hence λ 1 = λ 2 are the smallest eigenvalues. Now the upper bound follows from the Hoffman bound (1):

$$\frac { - \lambda _ { m i n } } { d - \lambda _ { m i n } } = \frac { 1 } { k ^ { 2 } - k + 1 } = \frac { \binom { n - 2 } { k - 2 } } { \binom { n } { k } }.$$

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00484v1-figure-07943cfb-e7e9-4977-b165-270dc3759cb5.jpg)

## 4 Discussion

Let us briefly discuss the sporadic nature of the result. In all solved cases maximal independent sets form designs or juntas. Hoffman bound is tight when the corresponding characteristic vector belongs to maximal and minimal eigenspaces and it seems difficult to modify the method in other cases. The maximal eigenspace is always unique and corresponds to the all-unit vector. For t ≥ 1 the characteristic vectors of all known examples belong to more than two eigenspaces, so several minimal eigenvalues should coincide in order to use Hoffman bound. Summing up, it seems that the only case is t = 1 , in which we have an example with the characteristic vector in the first three eigenspaces. So we need λ 1 = λ 2 which implies n = k 2 -k +1 .

## 4.1 Finite projective planes

If k -1 is a prime power, then one can prove the upper bound in Theorem 1 combinatorially. Since Johnson graphs are vertex-transitive (moreover they are edge-transitive), one has

$$w ( J ) \cdot \alpha ( J ) \leq | V ( J ) |.$$

In our case k 2 -k +1 is the size of a projective plane over GF k ( -1) , and so w J k ( [ 2 -k +1]) ≥ k 2 -k +1 . This immediately implies the bound.

However for a composite k -1 the corresponding construction may not exist. A major negative result is a celebrated Bruck-Ryser theorem [3] which states that if n is a positive integer of the form 4 k +1 or 4 k +2 and n is not equal to the sum of two integer squares, then n does not occur as the order of a finite plane. A widely known conjecture is that the order of a finite plane is always a prime power. Also, the non-existence of a finite plane of order 10 was proven by Lam [14].

## 4.2 Uniqueness

For k = 3 the graph J (7 , 3 1) , has a maximal independent set of another structure, namely

$$\{ \{ 1, 2, 3 \}, \{ 1, 2, 4 \}, \{ 1, 3, 4 \}, \{ 2, 3, 4 \}, \{ 5, 6, 7 \} \}.$$

For other values of k it seems very likely that every maximal independent set of J k ( 2 -k + 1 , k, 1) forms a family with two elements in common. However we are not able to prove it. Following the proof of Theorem 1, an independent set I of the maximal size satisfies the equality in (2) and thus χ I belongs to the zeroth, the first and the second eigenspaces. Main obstacle in our attempt is a relatively complicated structure of the second eigenspace.

Acknowledgements. The research is supported by Bulgarian NSF grant KP-06-N72/6-2023.

## References

| [1]   | Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 624-630, 2020.                            |
|-------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [2]   | Eiichi Bannai, Etsuko Bannai, Tatsuro Ito, and Rie Tanaka. Algebraic combinatorics , volume 5. Walter de Gruyter GmbH & Co KG, 2021.                                                                                                |
| [3]   | Richard H. Bruck and Herbert J. Ryser. The nonexistence of certain finite projective planes. Canadian Journal of Mathematics , 1(1):88-93, 1949.                                                                                    |
| [4]   | David Ellis, Nathan Keller, and Noam Lifshitz. Stability for the complete intersection theorem, and the forbidden intersection problem of Erd˝s o and S´s. o Journal of the European Mathematical Society , 26(5):1611- 1654, 2024. |
| [5]   | P. Erd˝s, o C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser.(2) , 12:313-320, 1961.                                                                                                |
| [6]   | P. Frankl and Z. F¨redi. u Forbidding just one intersection. Journal of Combinatorial Theory, Series A , 39(2):160-176, 1985.                                                                                                       |
| [7]   | P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica , 1(4):357- 368, 1981.                                                                                                                 |
| [8]   | Christopher Godsil and Karen Meagher. Erd˝s-Ko-Rado o theorems: algebraic approaches , volume 149. Cambridge University Press, 2016.                                                                                                |
| [9]   | Willem H. Haemers. Hoffman's ratio bound. Linear Algebra and its Applications , 617:215-219, 2021.                                                                                                                                  |
| [10]  | J. Kahn and G. Kalai. A counterexample to Borsuk's conjecture. Bulletin of the American Mathematical Society , 29(1):60-62, 1993.                                                                                                   |
| [11]  | Peter Keevash, Dhruv Mubayi, and Richard M. Wilson. Set systems with no singleton intersection. SIAM Journal on Discrete Mathematics , 20(4):1031-1041, 2006.                                                                       |
| [12]  | Nathan Keller and Noam Lifshitz. The junta method for hypergraphs and the Erd˝s-Chv´tal o a simplex conjecture. Advances in Mathematics , 392:107991, 2021.                                                                         |
| [13]  | Andrey Kupavskii and Dmitrii Zakharov. Spread approximations for forbidden intersections problems. Advances in Mathematics , 445:109653, 2024.                                                                                      |
| [14]  | Clement W. H. Lam. The search for a finite projective plane of order 10. The American Mathematical Monthly , 98(4):305-318, 1991.                                                                                                   |
| [15]  | L´szl´ a o Lov´sz. a On the Shannon capacity of a graph. IEEE Transactions on Information Theory , 25(1):1-7, 1979.                                                                                                                 |
| [16]  | A. M. Raigorodskii. Borsuk's problem and the chromatic numbers of some metric spaces. Russian Mathe- matical Surveys , 56(1):103, 2001.                                                                                             |
Danila Cherkashin
On set systems without singleton intersections
Consider a family $\mathcal{F}$ of $k$-subsets of an ambient $(k^2-k+1)$-set
such that no pair of $k$-subsets in $\mathcal{F}$ intersects in exactly one
element. In this short note we show that the maximal size of such $\mathcal{F}$
is $\binom{k^2-k-1}{k-2}$ for every $k > 1$.