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.

Revised:

Accepted:

Published online:

Keywords: Chromatic number, independence ratio, hypergraph, extremal set theory.

^{1}; Golubev, Konstantin

^{2}; Lifshitz, Noam

^{3}

@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 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 -

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] Contributions to the geometry of Hamming spaces, Discrete Math., Volume 17 (1977) no. 1, pp. 1-22 | DOI | MR | Zbl

[2] Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., Volume 14 (2004) no. 5, pp. 913-940 | DOI | MR | Zbl

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

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

[5] 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] 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] An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973) no. 10, p. vi+97 | MR | Zbl

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

[9] 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] Conditional hardness for approximate coloring, SIAM J. Comput., Volume 39 (2009) no. 3, pp. 843-873 | DOI | MR | Zbl

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

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

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

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

[15] Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Volume 12 (1961), pp. 313-320 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

[24] 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] 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] On the chromatic number of a simplicial complex, Combinatorica, Volume 37 (2017) no. 5, pp. 953-964 | DOI | MR | Zbl

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

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

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

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

[31] On some extensions of the FKN theorem, Theory Comput., Volume 11 (2015), pp. 445-469 | DOI | MR | Zbl

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

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

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

[35] 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] 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] 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] 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

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

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

[42] Isoperimetric inequalities in simplicial complexes, Combinatorica, Volume 36 (2016) no. 2, pp. 195-227 | DOI | MR | Zbl

[43] 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] 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] Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B, Volume 126 (2017), pp. 137-161 | DOI | MR | Zbl

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

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

[48] 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: *