High dimensional Hoffman bound and applications in extremal combinatorics
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: https://doi.org/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.
@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
DA  - 2021///
SP  - 1005
EP  - 1026
VL  - 4
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.190/
UR  - https://doi.org/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://doi.org/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 | Article | MR 465883 | Zbl 0368.05001

[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 | Article | MR 2105948 | Zbl 1056.05104

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

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

[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 | Article | MR 3856707 | Zbl 1397.05098

[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 | Article | MR 2344981 | Zbl 1125.05053

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

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

[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 | Article | MR 2399096 | Zbl 1147.05058

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

[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 | Article | MR 2178966 | Zbl 1084.68051

[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 | Article | MR 2911886 | Zbl 1238.05143

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

[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 260599 | Zbl 0136.21302

[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 | Article | MR 140419 | Zbl 0100.01902

[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 | Article | MR 3874601 | Zbl 1401.05317

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

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

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

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

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

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

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

[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 | Article | MR 2269550 | Zbl 1105.94027

[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 | Article | MR 3497070 | Zbl 1343.05002

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

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

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

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

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

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

[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 | Article | MR 3549622 | Zbl 1348.05193

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

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

[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 | Article | MR 439403 | Zbl 0361.94016

[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 | Article | MR 1335785 | Zbl 0832.11006

[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 | Article | MR 2630040 | Zbl 1201.60031

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

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

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

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

[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 | Article | MR 2236252 | Zbl 1298.94152

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

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

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

[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: