ALGEBRAIC COMBINATORICS

no. 3
Application of hypergraph Hoffman’s bound to intersecting families
Tokushige, Norihide1
1 University of the Ryukyus College of Education 1 Senbaru Nishihara Okinawa 903-0213, Japan
Algebraic Combinatorics, Volume 5 (2022) no. 3, pp. 537-557.

Using the Filmus–Golubev–Lifshitz method [7] to bound the independence number of a hypergraph, we solve some problems concerning multiply intersecting families with biased measures. Among other results we obtain a stability result of a measure version of the Erdős–Ko–Rado theorem for multiply intersecting families.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.222
Classification: 05D05, 05C50, 05C69
Keywords: Hoffman’s bound, intersecting family, independence number, boolean function.
Tokushige, Norihide 1

1 University of the Ryukyus College of Education 1 Senbaru Nishihara Okinawa 903-0213, Japan
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_3_537_0,
     author = {Tokushige, Norihide},
     title = {Application of hypergraph {Hoffman{\textquoteright}s} bound to intersecting families},
     journal = {Algebraic Combinatorics},
     pages = {537--557},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {3},
     year = {2022},
     doi = {10.5802/alco.222},
     zbl = {07555119},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.222/}
}
TY  - JOUR
AU  - Tokushige, Norihide
TI  - Application of hypergraph Hoffman’s bound to intersecting families
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 537
EP  - 557
VL  - 5
IS  - 3
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.222/
DO  - 10.5802/alco.222
LA  - en
ID  - ALCO_2022__5_3_537_0
ER  - 
%0 Journal Article
%A Tokushige, Norihide
%T Application of hypergraph Hoffman’s bound to intersecting families
%J Algebraic Combinatorics
%D 2022
%P 537-557
%V 5
%N 3
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.222/
%R 10.5802/alco.222
%G en
%F ALCO_2022__5_3_537_0
Tokushige, Norihide. Application of hypergraph Hoffman’s bound to intersecting families. Algebraic Combinatorics, Volume 5 (2022) no. 3, pp. 537-557. doi : 10.5802/alco.222. https://alco.centre-mersenne.org/articles/10.5802/alco.222/

[1] Ahlswede, Rudolf; Katona, Gyula O. H. Contributions to the geometry of Hamming spaces, Discrete Math., Volume 17 (1977) no. 1, pp. 1-22 | DOI | MR | Zbl

[2] Ahlswede, Rudolf; Khachatrian, Levon H. The diametric theorem in Hamming spaces—optimal anticodes, Adv. in Appl. Math., Volume 20 (1998) no. 4, pp. 429-449 | DOI | MR | Zbl

[3] Bey, Christian; Engel, Konrad Old and new results for the weighted t-intersection problem via AK-methods, Numbers, information and complexity (Bielefeld, 1998), Kluwer Acad. Publ., Boston, MA, 2000, pp. 45-74 | MR | Zbl

[4] Borg, Peter Cross-intersecting integer sequences (2012) (https://arxiv.org/abs/1212.6955)

[5] Brace, Alan; Daykin, David E. A finite set covering theorem, Bull. Austral. Math. Soc., Volume 5 (1971), pp. 197-202 | DOI | MR | Zbl

[6] Filmus, Yuval; Golubev, Konstantin; Lifshitz, Noam High dimensional Hoffman bound (2020) (https://yuvalfilmus.cs.technion.ac.il/Talks/Hoffman.pdf)

[7] Filmus, Yuval; Golubev, Konstantin; Lifshitz, Noam High dimensional Hoffman bound and applications in extremal combinatorics, Algebr. Comb., Volume 4 (2021) no. 6, pp. 1005-1026 | MR

[8] Fishburn, Peter C.; Frankl, Peter; Freed, Daniel; Lagarias, Jeffrey C.; Odlyzko, Andrew M. Probabilities for intersecting systems and random subsets of finite sets, SIAM J. Algebraic Discrete Methods, Volume 7 (1986) no. 1, pp. 73-79 | DOI | MR | Zbl

[9] Frankl, Peter; Tokushige, Norihide Weighted multiply intersecting families, Studia Sci. Math. Hungar., Volume 40 (2003) no. 3, pp. 287-291 | DOI | MR | Zbl

[10] Frankl, Peter; Tokushige, Norihide Extremal problems for finite sets, Student Mathematical Library, 86, American Mathematical Society, Providence, RI, 2018, viii+224 pages | DOI | MR | Zbl

[11] Friedgut, Ehud On the measure of intersecting families, uniqueness and stability, Combinatorica, Volume 28 (2008) no. 5, pp. 503-528 | DOI | MR | Zbl

[12] Friedgut, Ehud; Kalai, Gil; Naor, Assaf Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math., Volume 29 (2002) no. 3, pp. 427-437 | DOI | MR | Zbl

[13] Haemers, Willem H. Hoffman’s ratio bound (2021) (https://arxiv.org/abs/2102.05529)

[14] Kindler, Guy Property testing, PCP, and Juntas, Ph. D. Thesis, Tel Aviv University (2002)

[15] Kindler, Guy; Safra, Shmuel Noise-Resistant Boolean-Functions are Juntas (2004) (https://www.cs.huji.ac.il/w~gkindler/)

[16] Suda, Sho; Tanaka, Hajime; Tokushige, Norihide A semidefinite programming approach to a cross-intersection problem with measures, Math. Program., Volume 166 (2017) no. 1-2, Ser. A, pp. 113-130 | DOI | MR | Zbl

Cited by Sources: