ALGEBRAIC COMBINATORICS

no. 6
High dimensional Hoffman bound and applications in extremal combinatorics
Filmus, Yuval1; Golubev, Konstantin2; Lifshitz, Noam3
1 The Henry and Marilyn Taub Faculty of Computer Science Technion — Israel Institute of Technology, Haifa Israel.
2 D-MATH, ETH Zurich, Switzerland. Moscow Center for Fundamental and Applied Mathematics, Russia.
3 Einstein Institute of Mathematics Hebrew University, Jerusalem Israel.
Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 1005-1026.

The n-th tensor power of a graph with vertex set V is the graph on the vertex set V n , where two vertices are connected by an edge if they are connected in each coordinate. One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of its eigenvalues. In this paper we introduce the problem of upper-bounding independent sets in tensor powers of hypergraphs. We show that many prominent open problems in extremal combinatorics, such as the Turán problem for graphs and hypergraphs, can be encoded as special cases of this problem. We generalize the Hoffman bound to hypergraphs, and give several applications.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.190
Classification: 05C15, 05C65, 05D05
Keywords: Chromatic number, independence ratio, hypergraph, extremal set theory.
Filmus, Yuval 1; Golubev, Konstantin 2; Lifshitz, Noam 3

1 The Henry and Marilyn Taub Faculty of Computer Science Technion — Israel Institute of Technology, Haifa Israel.
2 D-MATH, ETH Zurich, Switzerland. Moscow Center for Fundamental and Applied Mathematics, Russia.
3 Einstein Institute of Mathematics Hebrew University, Jerusalem Israel.
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2021__4_6_1005_0,
     author = {Filmus, Yuval and Golubev, Konstantin and Lifshitz, Noam},
     title = {High dimensional {Hoffman} bound and applications in extremal combinatorics},
     journal = {Algebraic Combinatorics},
     pages = {1005--1026},
     publisher = {MathOA foundation},
     volume = {4},
     number = {6},
     year = {2021},
     doi = {10.5802/alco.190},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.190/}
}
TY  - JOUR
AU  - Filmus, Yuval
AU  - Golubev, Konstantin
AU  - Lifshitz, Noam
TI  - High dimensional Hoffman bound and applications in extremal combinatorics
JO  - Algebraic Combinatorics
PY  - 2021
SP  - 1005
EP  - 1026
VL  - 4
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.190/
DO  - 10.5802/alco.190
LA  - en
ID  - ALCO_2021__4_6_1005_0
ER  - 
%0 Journal Article
%A Filmus, Yuval
%A Golubev, Konstantin
%A Lifshitz, Noam
%T High dimensional Hoffman bound and applications in extremal combinatorics
%J Algebraic Combinatorics
%D 2021
%P 1005-1026
%V 4
%N 6
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.190/
%R 10.5802/alco.190
%G en
%F ALCO_2021__4_6_1005_0
Filmus, Yuval; Golubev, Konstantin; Lifshitz, Noam. High dimensional Hoffman bound and applications in extremal combinatorics. Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 1005-1026. doi : 10.5802/alco.190. https://alco.centre-mersenne.org/articles/10.5802/alco.190/

[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] Alon, Noga; Dinur, Irit; Friedgut, Ehud; Sudakov, Benny Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., Volume 14 (2004) no. 5, pp. 913-940 | DOI | MR | Zbl

[3] Alon, Noga; Lubetzky, Eyal Independent sets in tensor graph powers, J. Graph Theory, Volume 54 (2007) no. 1, pp. 73-87 | DOI | MR | Zbl

[4] Bachoc, Christine; Gundert, Anna; Passuello, Alberto The theta number of simplicial complexes, Israel J. Math., Volume 232 (2019) no. 1, pp. 443-481 | DOI | MR | Zbl

[5] Brouwer, Andries E.; Cioabă, Sebastian M.; Ihringer, Ferdinand; McGinnis, Matt The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters, J. Combin. Theory Ser. B, Volume 133 (2018), pp. 88-121 | DOI | MR | Zbl

[6] de Klerk, Etienne; Pasechnik, Dmitrii V. A note on the stability number of an orthogonality graph, European J. Combin., Volume 28 (2007) no. 7, pp. 1971-1979 | DOI | MR | Zbl

[7] Delsarte, Phillippe An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973) no. 10, p. vi+97 | MR | Zbl

[8] Dinur, Irit; Friedgut, Ehud Intersecting families are essentially contained in juntas, Combin. Probab. Comput., Volume 18 (2009) no. 1-2, pp. 107-122 | DOI | MR | Zbl

[9] Dinur, Irit; Friedgut, Ehud; Regev, Oded Independent sets in graph powers are almost contained in juntas, Geom. Funct. Anal., Volume 18 (2008) no. 1, pp. 77-97 | DOI | MR | Zbl

[10] Dinur, Irit; Mossel, Elchanan; Regev, Oded Conditional hardness for approximate coloring, SIAM J. Comput., Volume 39 (2009) no. 3, pp. 843-873 | DOI | MR | Zbl

[11] Dinur, Irit; Safra, Samuel On the hardness of approximating minimum vertex cover, Ann. of Math. (2), Volume 162 (2005) no. 1, pp. 439-485 | DOI | MR | Zbl

[12] Ellis, David; Filmus, Yuval; Friedgut, Ehud Triangle-intersecting families of graphs, J. Eur. Math. Soc. (JEMS), Volume 14 (2012) no. 3, pp. 841-885 | DOI | MR | Zbl

[13] Ellis, David; Friedgut, Ehud; Pilpel, Haran Intersecting families of permutations, J. Amer. Math. Soc., Volume 24 (2011) no. 3, pp. 649-682 | DOI | MR | Zbl

[14] Erdős, Paul A problem on independent r-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., Volume 8 (1965), pp. 93-95 | MR | Zbl

[15] Erdős, Paul; Ko, Chao; Rado, Richard Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Volume 12 (1961), pp. 313-320 | DOI | MR | Zbl

[16] Filmus, Yuval; Ihringer, Ferdinand Boolean degree 1 functions on some classical association schemes, J. Combin. Theory Ser. A, Volume 162 (2019), pp. 241-270 | DOI | MR | Zbl

[17] Frankl, Péter On Sperner families satisfying an additional condition, J. Combinatorial Theory Ser. A, Volume 20 (1976) no. 1, pp. 1-11 | DOI | MR | Zbl

[18] Frankl, Péter Asymptotic solution of a Turán-type problem, Graphs Combin., Volume 6 (1990) no. 3, pp. 223-227 | DOI | MR | Zbl

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

[20] Friedgut, Ehud Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, Volume 18 (1998) no. 1, pp. 27-35 | DOI | MR | Zbl

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

[22] Friedgut, Ehud; Regev, Oded Kneser graphs are like Swiss cheese, Discrete Anal. (2018), Paper no. 2, 18 pages | DOI | MR | Zbl

[23] Gijswijt, Dion Matrix Algebras and Semidefinite Programming Techniques for Codes, Ph. D. Thesis, University of Amsterdam (2005)

[24] Gijswijt, Dion; Schrijver, Alexander; Tanaka, Hajime New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming, J. Combin. Theory Ser. A, Volume 113 (2006) no. 8, pp. 1719-1731 | DOI | MR | Zbl

[25] Godsil, Chris; Meagher, Karen Erdős–Ko–Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, 149, Cambridge University Press, Cambridge, 2016, xvi+335 pages | DOI | MR | Zbl

[26] Golubev, Konstantin On the chromatic number of a simplicial complex, Combinatorica, Volume 37 (2017) no. 5, pp. 953-964 | DOI | MR | Zbl

[27] Golubev, Konstantin; Parzanchevski, Ori Spectrum and combinatorics of two-dimensional Ramanujan complexes, Israel J. Math., Volume 230 (2019) no. 2, pp. 583-612 | DOI | MR | Zbl

[28] Gundert, Anna; Szedlák, May Higher dimensional discrete Cheeger inequalities, J. Comput. Geom., Volume 6 (2015) no. 2, pp. 54-71 | DOI | MR | Zbl

[29] Haemers, Willem A generalization of the Higman-Sims technique, Nederl. Akad. Wetensch. Indag. Math., Volume 40 (1978) no. 4, pp. 445-447 | DOI | MR

[30] Hoffman, Alan J. On eigenvalues and colorings of graphs, Selected Papers of Alan J. Hoffman — with Commentary, World Scientific, 2003, pp. 407-419 | DOI

[31] Jendrej, Jacek; Oleszkiewicz, Krzysztof; Wojtaszczyk, Jakub O. On some extensions of the FKN theorem, Theory Comput., Volume 11 (2015), pp. 445-469 | DOI | MR | Zbl

[32] Linial, Nathan; Peled, Yuval On the phase transition in random simplicial complexes, Ann. of Math. (2), Volume 184 (2016) no. 3, pp. 745-773 | DOI | MR | Zbl

[33] Lovász, László On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, Volume 25 (1979) no. 1, pp. 1-7 | DOI | MR | Zbl

[34] Lubotzky, Alexander Ramanujan complexes and high dimensional expanders, Jpn. J. Math., Volume 9 (2014) no. 2, pp. 137-169 | DOI | MR | Zbl

[35] Mantel, Willem Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff), Wiskundige Opgaven, Volume 10 (1907), pp. 60-61

[36] McEliece, Robert J.; Rodemich, Eugene R.; Rumsey, Howard Jr.; Welch, Lloyd R. New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities, IEEE Trans. Inform. Theory, Volume IT-23 (1977) no. 2, pp. 157-166 | DOI | MR | Zbl

[37] Meshulam, Roy On subsets of finite abelian groups with no 3-term arithmetic progressions, J. Combin. Theory Ser. A, Volume 71 (1995) no. 1, pp. 168-172 | DOI | MR | Zbl

[38] Mossel, Elchanan; O’Donnell, Ryan; Oleszkiewicz, Krzysztof Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2), Volume 171 (2010) no. 1, pp. 295-341 | DOI | MR | Zbl

[39] Navon, Michael; Samorodnitsky, Alex Linear programming bounds for codes via a covering argument, Discrete Comput. Geom., Volume 41 (2009) no. 2, pp. 199-207 | DOI | MR | Zbl

[40] Parzanchevski, Ori Mixing in high-dimensional expanders, Combin. Probab. Comput., Volume 26 (2017) no. 5, pp. 746-761 | DOI | MR | Zbl

[41] Parzanchevski, Ori; Rosenthal, Ron Simplicial complexes: spectrum, homology and random walks, Random Structures Algorithms, Volume 50 (2017) no. 2, pp. 225-261 | DOI | MR | Zbl

[42] Parzanchevski, Ori; Rosenthal, Ron; Tessler, Ran J. Isoperimetric inequalities in simplicial complexes, Combinatorica, Volume 36 (2016) no. 2, pp. 195-227 | DOI | MR | Zbl

[43] Schrijver, Alexander A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, Volume 25 (1979) no. 4, pp. 425-429 | DOI | MR | Zbl

[44] Schrijver, Alexander New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory, Volume 51 (2005) no. 8, pp. 2859-2866 | DOI | MR | Zbl

[45] Tait, Michael; Tobin, Josh Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B, Volume 126 (2017), pp. 137-161 | DOI | MR | Zbl

[46] Weichsel, Paul M. The Kronecker product of graphs, Proc. Amer. Math. Soc., Volume 13 (1962), pp. 47-52 | DOI | MR | Zbl

[47] Wilson, Richard M. The exact bound in the Erdős–Ko–Rado theorem, Combinatorica, Volume 4 (1984) no. 2-3, pp. 247-257 | DOI | MR | Zbl

[48] Zhao, Yufei Graph theory and additive combinatorics (2019) (https://ocw.mit.edu/courses/mathematics/18-217-graph-theory-and-additive-combinatorics-fall-2019/lecture-notes/MIT18_217F19_full_notes.pdf)

Cited by Sources: