This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contains a subgraph that is isomorphic to a specified graph $ \mathsf{{H}} $. Such families are referred to as $ \mathsf{{H}} $-intersecting graph families. The bound is derived using the combinatorial version of Shearer's lemma, and it forms a nontrivial extension of the bound derived by Chung, Graham, Frankl, and Shearer (1986), where $ \mathsf{{H}} $ is specialized to a triangle. The derived bound is expressed in terms of the chromatic number of $ \mathsf{{H}} $, while a relaxed version, formulated using the Lovász $ \vartheta $-function of the complement of $ \mathsf{{H}} $, offers reduced computational complexity. Additionally, a probabilistic version of Shearer's lemma, combined with properties of Shannon entropy, are employed to establish bounds related to the enumeration of graph homomorphisms, providing further insights into the interplay between combinatorial structures and information-theoretic principles.
Citation: Igal Sason. On $ \mathsf{{H}} $-intersecting graph families and counting of homomorphisms[J]. AIMS Mathematics, 2025, 10(3): 6355-6378. doi: 10.3934/math.2025290
This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contains a subgraph that is isomorphic to a specified graph $ \mathsf{{H}} $. Such families are referred to as $ \mathsf{{H}} $-intersecting graph families. The bound is derived using the combinatorial version of Shearer's lemma, and it forms a nontrivial extension of the bound derived by Chung, Graham, Frankl, and Shearer (1986), where $ \mathsf{{H}} $ is specialized to a triangle. The derived bound is expressed in terms of the chromatic number of $ \mathsf{{H}} $, while a relaxed version, formulated using the Lovász $ \vartheta $-function of the complement of $ \mathsf{{H}} $, offers reduced computational complexity. Additionally, a probabilistic version of Shearer's lemma, combined with properties of Shannon entropy, are employed to establish bounds related to the enumeration of graph homomorphisms, providing further insights into the interplay between combinatorial structures and information-theoretic principles.
| [1] | M. Simonovits, V. T. Sós, Intersection theorems for graphs II, In: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely), vol. Ⅱ, Colloq. Math. Soc. János Bolyai, 18, North-Holland Publishing Co., Amsterdam-New York, 1976, 1017–1030. Available from: https://users.renyi.hu/sos/1976_Intersection_Theorems_for_Graphs_II.pdf. |
| [2] | M. Simonovits, V. T. Sós, Intersection theorems for graphs, Problèmes combinatoires et théorie des graphes, Colloq. CNRS, 260 (1978), 389–391. Available from: https://users.renyi.hu/miki/OrsayB.pdf. |
| [3] |
M. Simonovits, V. T. Sós, Intersection theorems on structures, Ann. Discrete Math., 6 (1980), 301–313. https://doi.org/10.1016/S0167-5060(08)70715-5 doi: 10.1016/S0167-5060(08)70715-5
|
| [4] |
F. R. K. Chung, L. R. Graham, P. Frankl, J. B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A, 43 (1986), 23–37. https://doi.org/10.1016/0097-3165(86)90019-1 doi: 10.1016/0097-3165(86)90019-1
|
| [5] |
D. Ellis, Y. Filmus, E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc., 14 (2012), 841–855. https://doi.org/10.4171/JEMS/320 doi: 10.4171/JEMS/320
|
| [6] | D. Ellis, Intersection problems in extremal combinatorics: Theorems, techniques, and questions-old and new, In: Surveys in Combinatorics 2022, London Math. Soc. Lecture Note Ser., Cambridge University Press, 2022,115–173. https://doi.org/10.1017/9781009093927.005 |
| [7] |
A. Berger, Y. Zhao, $K_4$-intersecting families of graphs, J. Combin. Theory Ser. B, 163 (2023), 112–132. https://doi.org/10.1016/j.jctb.2023.07.005 doi: 10.1016/j.jctb.2023.07.005
|
| [8] |
N. Keller, N. Lifshitz, A note on large $H$-intersecting families, SIAM J. Discrete Math., 33 (2019), 398–401. https://doi.org/10.1137/18M1220765 doi: 10.1137/18M1220765
|
| [9] | M. Aigner, G. M. Ziegler, Proofs from THE BOOK, 6 Eds., Springer, Berlin, 2018. https://doi.org/10.1007/978-3-662-57265-8 |
| [10] | S. Jukna, Extremal combinatorics with applications in computer science, 2 Eds., Springer Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-17364-6 |
| [11] | D. Galvin, Three tutorial lectures on entropy and counting, In: Proc. 1st Lake Michigan Workshop on Combin. and Graph Theory, Kalamazoo, MI, 2014. https://doi.org/10.48550/arXiv.1406.7872 |
| [12] |
N. Pippenger, An information-theoretic method in combinatorial theory, J. Combin. Theory Ser. A, 23 (1977), 99–104. https://doi.org/10.1016/0097-3165(77)90083-8 doi: 10.1016/0097-3165(77)90083-8
|
| [13] |
N. Pippenger, Entropy and enumeration of Boolean functions, IEEE Trans. Inform. Theory, 45 (1999), 2096–2100. https://doi.org/10.1109/18.782146 doi: 10.1109/18.782146
|
| [14] |
J. Radhakrishnan, An entropy proof of Bregman's theorem, J. Combin. Theory Ser. A, 77 (1997), 161–164. https://doi.org/10.1006/jcta.1996.2727 doi: 10.1006/jcta.1996.2727
|
| [15] | J. Radhakrishnan, Entropy and counting, In: Proc. IIT Kharagpur Golden Jubilee Volume on Computational Mathematics, Modelling and Algorithms, Narosa Publ., New Delhi, 2001, 1–25. Available from: https://www.tcs.tifr.res.in/jaikumar/Papers/EntropyAndCounting.pdf. |
| [16] | E. Friedgut, Hypergraphs, entropy, and inequalities, Am. Math. Mon., 111 (2004), 749–760. https://doi.org/10.2307/4145187 |
| [17] |
D. Gavinsky, S. Lovett, M. Saks, S. Srinivasan, A tail bound for read-$k$ families of functions, Random Struct. Algor., 47 (2015), 99–108. http://doi.org/10.1002/rsa.20532 doi: 10.1002/rsa.20532
|
| [18] |
J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Comb. Probab. Comput., 10 (2001), 219–237. https://doi.org/10.1017/S0963548301004631 doi: 10.1017/S0963548301004631
|
| [19] |
J. Kahn, Entropy, independent sets and antichains: A new approach to Dedekind's problem, Proc. AMS, 130 (2001), 371–378. https://doi.org/10.1090/S0002-9939-01-06058-0 doi: 10.1090/S0002-9939-01-06058-0
|
| [20] |
M. Madiman, P. Tetali, Information inequalities for joint distributions, interpretations and applications, IEEE T. Inform. Theory, 56 (2010), 2699–2713. https://doi.org/10.1109/TIT.2010.2046253 doi: 10.1109/TIT.2010.2046253
|
| [21] |
I. Sason, A generalized information-theoretic approach for bounding the number of independent sets in bipartite graphs, Entropy, 23 (2021), 1–14. https://doi.org/10.3390/e23030270 doi: 10.3390/e23030270
|
| [22] |
I. Sason, Information inequalities via submodularity, and a problem in extremal graph theory, Entropy, 24 (2022), 1–31. https://doi.org/10.3390/e24050597 doi: 10.3390/e24050597
|
| [23] | I. Sason, Combinatorial applications of the Shearer and Han inequalities in graph theory and Boolean functions, In: Workshop on Information Theory, Boolean Functions, and Lattice Problems, Hausdorff Research Institute for Mathematics (HIM), Bonn, Germany, November 18–22, 2024. The recorded talk is at https://www.youtube.com/watch?v=D-poDm7AnLU |
| [24] |
G. Brightwell, P. Winkler, Graph homomorphisms and phase transitions, J. Comb. Theory B, 77 (1999), 221–262. https://doi.org/10.1006/jctb.1999.1899 doi: 10.1006/jctb.1999.1899
|
| [25] | P. Hell, J. Neštril, Graphs and homomorphisms, Oxford University Press, 2004. https://doi.org/10.1093/acprof: oso/9780198528173.001.0001 |
| [26] | C. Borgs, J. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi, Counting graph homomorphisms, Topics in Discrete Mathematics, Springer, 2006,315–371. https://doi.org/10.1093/acprof: oso/9780198528173.001.0001 |
| [27] | P. Csikvári, N. Ruozzi, S. Shams, Markov random fields, homomorphism counting, and Sidorenko's conjecture, IEEE T. Inform. Theory, 68 (2022), 6052–6062. https://doi.org/10.1109/TIT.2022.3169487 |
| [28] |
E. Friedgut, J. Kahn, On the number of copies of one hypergraph in another, Israel J. Math., 105 (1998), 251–256. https://doi.org/10.1007/BF02780332 doi: 10.1007/BF02780332
|
| [29] | L. Lovász, Large networks and graph limits, American Mathematical Society, 2012. https://doi.org/10.1090/coll/060 |
| [30] | Z. Wang, J. Tu, R. Lang, Entropy, graph homomorphisms, and dissociation sets, Entropy, 25 (2023), 1–11. https://doi.org/10.3390/e25010163 |
| [31] | Y. Zhao, Graph theory and additive combinatorics: Exploring structures and randomness, Cambridge University Press, 2023. https://doi.org/10.1017/9781009310956 |
| [32] | T. M. Cover, J. A. Thomas, Elements of information theory, second edition, John Wiley & Sons, 2006. https://doi.org/10.1002/047174882X |
| [33] |
T. S. Han, Nonnegative entropy measures of multivariate symmetric correlations, Inform. Control, 36 (1978), 133–156. https://doi.org/10.1016/S0019-9958(78)90275-9 doi: 10.1016/S0019-9958(78)90275-9
|
| [34] |
N. Alon, On the number of subgraphs of prescribed type of graphs with a given number of edges, Israel J. Math., 38 (1981), 116–130. https://doi.org/10.1007/BF02761855 doi: 10.1007/BF02761855
|
| [35] | M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, 1979. |
| [36] |
L. Lovász, On the Shannon capacity of a graph, IEEE T. Inform. Theory, 25 (1979), 1–7. https://doi.org/10.1109/TIT.1979.1055985 doi: 10.1109/TIT.1979.1055985
|
| [37] |
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 168–197. https://doi.org/10.1007/BF02579273 doi: 10.1007/BF02579273
|
| [38] | D. E. Knuth, The sandwich theorem, Electron. J. Combin., 1 (1994), 1–48. https://doi.org/10.37236/1193 |
| [39] | L. Lovász, Graphs and geometry, American Mathematical Society, 65 (2019). https://doi.org/10.1090/coll/065 |
| [40] |
I. Sason, Observations on graph invariants with the Lovász $\vartheta$-function, AIMS Math., 9 (2024), 15385–15468. https://doi.org/10.3934/math.2024747 doi: 10.3934/math.2024747
|
| [41] | A. E. Brouwer, H. Van Maldeghem, Strongly regular graphs, Cambridge University Press, (Encyclopedia of Mathematics and its Applications, Series Number 182), 2022. https://doi.org/10.1017/9781009057226 |
| [42] | J. H. van Lint, R. M. Wilson, A course in combinatorics, 2 Eds., Cambridge University Press, 2001. https://doi.org/10.1017/CBO9780511987045 |
| [43] |
I. Sason, Observations on the Lovász $\vartheta$-function, graph capacity, eigenvalues, and strong products, Entropy, 25 (2023), 1–40. https://doi.org/10.3390/e25010104 doi: 10.3390/e25010104
|
| [44] |
I. Sason, On strongly regular graphs and the friendship theorem, Mathematics, 13 (2025), 970. https://doi.org/10.3390/math13060970 doi: 10.3390/math13060970
|
| [45] | L. Lovász, Perfect graphs, In: Selected Topics in Graph Theory 2, Academic Press, 1983, 55–87. |
Igal Sason. On $ \mathsf{{H}} $-intersecting graph families and counting of homomorphisms[J]. AIMS Mathematics, 2025, 10(3): 6355-6378. doi: 10.3934/math.2025290
DownLoad: