Back to Search
Start Over
Threshold graphs maximise homomorphism densities.
- Source :
- Combinatorics, Probability & Computing; May2024, Vol. 33 Issue 3, p300-318, 19p
- Publication Year :
- 2024
-
Abstract
- Given a fixed graph $H$ and a constant $c \in [0,1]$ , we can ask what graphs $G$ with edge density $c$ asymptotically maximise the homomorphism density of $H$ in $G$. For all $H$ for which this problem has been solved, the maximum is always asymptotically attained on one of two kinds of graphs: the quasi-star or the quasi-clique. We show that for any $H$ the maximising $G$ is asymptotically a threshold graph, while the quasi-clique and the quasi-star are the simplest threshold graphs, having only two parts. This result gives us a unified framework to derive a number of results on graph homomorphism maximisation, some of which were also found quite recently and independently using several different approaches. We show that there exist graphs $H$ and densities $c$ such that the optimising graph $G$ is neither the quasi-star nor the quasi-clique (Day and Sarkar, SIAM J. Discrete Math. 35(1), 294–306, 2021). We also show that for $c$ large enough all graphs $H$ maximise on the quasi-clique (Gerbner et al., J. Graph Theory 96(1), 34–43, 2021), and for any $c \in [0,1]$ the density of $K_{1,2}$ is always maximised on either the quasi-star or the quasi-clique (Ahlswede and Katona, Acta Math. Hung. 32(1–2), 97–120, 1978). Finally, we extend our results to uniform hypergraphs. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPH theory
HOMOMORPHISMS
DENSITY
HYPERGRAPHS
Subjects
Details
- Language :
- English
- ISSN :
- 09635483
- Volume :
- 33
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Combinatorics, Probability & Computing
- Publication Type :
- Academic Journal
- Accession number :
- 177486485
- Full Text :
- https://doi.org/10.1017/S096354832300041X