Hostname: page-component-669899f699-cf6xr Total loading time: 0 Render date: 2025-05-01T00:51:57.961Z Has data issue: false hasContentIssue false
  • English
  • Français

Domination inequalities and dominating graphs

Part of: Graph theory Combinatorics

Published online by Cambridge University Press:  19 September 2024

DAVID CONLON  and
JOONKYUNG LEE
DAVID CONLON
Affiliation:
Department of Mathematics, California Institute of Technology, Pasadena, CA 91125, U.S.A. e-mail:[email protected]
JOONKYUNG LEE
Affiliation:
Department of Mathematics, Yonsei University, Yonsei-ro 50, Seoul, South Korea. e-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We say that a graph H dominates another graph H′ if the number of homomorphisms from H′ to any graph G is dominated, in an appropriate sense, by the number of homomorphisms from H to G. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs.

MSC classification

Primary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Secondary: 05C35: Extremal problems 05A20: Combinatorial inequalities
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 177 , Issue 1 , July 2024 , pp. 167 - 184
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Antolín Camarena, O., Csóka, E., Hubai, T., Lippner, G. and Lovász, L., Positive graphs. European J. Combin. 52 (2016), 290–301.CrossRefGoogle Scholar
Conlon, D., Fox, J. and Sudakov, B., An approximate version of Sidorenko’s conjecture. Geom. Funct. Anal. 20 (2010), 1354–1366.CrossRefGoogle Scholar
Conlon, D., Kim, J. H., Lee, C. and Lee, J., Some advances on Sidorenko’s conjecture. J. London Math. Soc. 98 (2018), 593–608.CrossRefGoogle Scholar
Conlon, D. and Lee, J., Finite reflection groups and graph norms. Adv. Math. 315 (2017), 130–165.CrossRefGoogle Scholar
Conlon, D. and Lee, J., Sidorenko’s conjecture for blow-ups. Discrete Anal. (2021), paper no. 2, 13 pp.Google Scholar
Coregliano, L. N., Left-cut-percolation and induced-Sidorenko bigraphs. ArXiv:2205.14703 [math.CO].Google Scholar
Coregliano, L. N. and Razborov, A. A., Biregularity in Sidorenko’s conjecture. ArXiv:2108.06599 [math.CO].Google Scholar
Erdős, P. and Simonovits, M., Compactness results in extremal graph theory. Combinatorica 2 (1982), 275–288.CrossRefGoogle Scholar
Garbe, F., Hladký, J. and Lee, J., Two remarks on graph norms. Discrete Comput. Geom. 67 (2022), 919–929.CrossRefGoogle ScholarPubMed
Hatami, H., Graph norms and Sidorenko’s conjecture. Israel J. Math. 175 (2010), 125–150.CrossRefGoogle Scholar
Kim, J. H., Lee, C. and Lee, J., Two approaches to Sidorenko’s conjecture. Trans. Amer. Math. Soc. 368 (2016), 5057–5074.CrossRefGoogle Scholar
Lee, J., On some graph densities in locally dense graphs. Random Structures Algorithms 58 (2021), 322–344.CrossRefGoogle Scholar
Lee, J. and Sidorenko, A., On graph norms for complex-valued functions. J. London Math. Soc. 106 (2022), 1501–1538.CrossRefGoogle Scholar
Li, J. X. and Szegedy, B., On the logarithmic calculus and Sidorenko’s conjecture. ArXiv:1107.1153 [math.CO].Google Scholar
Lovász, L., Graph homomorphisms: Open problems. Unpublished manuscript available at http://www.cs.elte.hu/.17ex~lovasz/problems.pdf (2008).Google Scholar
Lovász, L., Large networks and graph limits. Amer. Math. Soc. Colloq. Publ., 60 (American Mathematical Society, Providence, RI, 2012).Google Scholar
Sidorenko, A., A correlation inequality for bipartite graphs. Graphs Combin. 9 (1993), 201–204.CrossRefGoogle Scholar
Sidorenko, A., Inequalities for functionals generated by bipartite graphs. Discrete Math. Appl. 2 (1993), 489–504.Google Scholar
Sidorenko, A., Weakly norming graphs are edge-transitive. Combinatorica 40 (2020), 601–604.CrossRefGoogle Scholar
Sidorenko, A., personal communication.Google Scholar
Simonovits, M., Extremal graph problems, degenerate extremal problems, and supersaturated graphs. In Progress in Graph Theory (Waterloo, Ont., 1982), 419–437 (Academic Press, Toronto, ON, 1984).Google Scholar
Szegedy, B., An information theoretic approach to Sidorenko’s conjecture. ArXiv:1406.6738 [math.CO].Google Scholar