On set systems without singleton intersections

Danila Cherkashin

doi:10.47443/dml.2024.142

Author(s)

Danila Cherkashin Institute of Mathematics and Informatics, Bulgarian Academy of Sciences,Sofia,Bulgaria

Abstract

Consider a family F of k-subsets of an ambient (k2 k + 1)-set such that no pair of k-subsets in F intersects in exactly one element. In this article, it is shown that the maximum size of F is k2k k2 1 for every k > 1.

Publication Details

Page(s) 85-88

DOI 10.47443/dml.2024.142

Published Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords

Johnson scheme, Erdos–S os problem, finite projective planes.

References

Aljohani M.,Bamberg J.,Cameron P. J. .2018 .Synchronization and separation in the Johnson schemes. , 74(3) : 213-232.

Alweiss R.,Lovett S.,Wu K.,J. Zhang, K. .2020 .Improved bounds for the sunflower lemma. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, : 624-630.

Bannai E.,Ito T.,Tanaka R. .2021 .. , : .

Bermond J.-C.,Frankl P. .1977 .On a conjecture of Chv a´tal on m-intersecting hypergraphs. Bull. Lond. Math. Soc. 9, (3) : 310-312.

Bruck R. H.,Ryser H. J. .1949 .The nonexistence of certain finite projective planes, Canad. , 1(1) : 88-93.

Ellis D. .2024 .Stability for the complete intersection theorem, and the forbidden intersection problem of Erdo˝s and So´s, J. Eur. Math. Soc, 26(5) : 1611-1654.

Erdo P.,Ko C.,Rado R. .1961 .Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2, 12 : 313-320.

Frankl P. .1977 .On families of finite sets no two of which intersect in a singleton. Bull. Aust. Math. Soc, 17(1) : 125-134.

Frankl P.,Z. P. .1985 .F u¨redi. Forbidding just one intersection. J. Combin. Theory Ser. A, 39(2) : 160-176.

Frankl P. .1981 .Intersection theorems with geometric consequences. Combinatorica, 1(4) : 357-368.

Godsil C.,Meagher K.,Ko-Rado Theorems .2016 .Erdo˝s-. , : .

Haemers W. H. .2021 .Hoffman's ratio bound. Linear Algebra Appl, 617 : 215-219.

Kahn J.,Kalai G. .1993 .A counterexample to Borsuk's conjecture. Bull. Amer. Math. Soc, 29(1) : 60-62.

Keevash P.,Mubayi D. .2006 .Set systems with no singleton intersection. SIAM J. Discrete Math, 20(4) : 1031-1041.

Keller N. .2021 .The junta method for hypergraphs and the Erdo˝s-Chva´ tal simplex conjecture, Adv. , 392 : 107991.

Kupavskii A.,Zakharov D. .2024 .Spread approximations for forbidden intersections problems. , 445 : 109653.

Lam C. W. H. .1991 .The search for a finite projective plane of order 10, Amer. Math. Monthly, 98(4) : 305-318.

Lova L. .1979 .´ sz, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1) : 1-7.

A. M. Raigorodskii .2001 .Borsuk's problem and the chromatic numbers of some metric spaces. Russian Math. Surveys, 56(1) : 103-139.