Asymmetric results about graph homomorphisms
Lior Gishboliner, Eoin Hurley, Yuval Wigderson · 2025
Read Asymmetric results about graph homomorphisms by Lior Gishboliner, Eoin Hurley, Yuval Wigderson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-20278.txt.
Introduction
Lior Gishboliner, Eoin Hurley, and Yuval Wigderson prove new results in a 2025 paper on graph homomorphisms, maps between graphs that keep linked nodes linked. Many classic results say, in rough terms, that a triangle-free graph with set traits can be mapped into a small triangle-free graph. Threshold results give this when the graph is dense enough, and an approximate version gives it for all graphs when the map is allowed some slack.
The authors study uneven versions, where the traits demanded of the source and the target need not match. For one case, a graph with no short odd cycles and a set density maps into a small triangle-free graph whose size rests only on that density. The cycle demand can be loosened when the graph has bounded complexity of a set kind. The work also sharpens a known proof.
Catalog record
| CREATOR | Lior Gishboliner, Eoin Hurley, Yuval Wigderson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-20278
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymmetric results about graph homomorphisms Thanks: LG: Department of Mathematics, University of Toronto, Canada. Email: [email protected] . Research supported by an NSERC Discovery Grant. Thanks: EH: Mathematical Institute, University of Oxford, Oxford, United Kingdom. Email: [email protected] Thanks: YW: Institute for Theoretical Studies, ETH Zürich, Zürich, Switzerland. Email: yuval.wigderson @eth-its.ethz.ch . Research supported by Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich foundation. Lior Gishboliner, Eoin Hurley, Yuval Wigderson Abstract . Many important results in extremal graph theory can be roughly summarised as “if a triangle-free graph G G has certain properties, then it has a homomorphism to a triangle-free graph Γ \Gamma of bounded size”. For example, bounds on homomorphism thresholds give such a statement if G G has sufficiently high minimum degree, and the approximate homomorphism theorem gives such a statement for all G G , if one weakens the notion of homomorphism appropriately. In this paper, we study asymmetric versions of these results, where the assumptions on G G and Γ \Gamma need not match. For example, we prove that if G G is a graph with odd girth at least 9 9 and minimum degree at least δ | G | \delta\lvert G\rvert , then G G is homomorphic to a triangle-free graph whose size depends only on δ \delta . Moreover, the odd girth assumption can be weakened to odd girth at least 7 7 if G G has bounded VC dimension or bounded domination number. This gives a new and improved proof of a result of Huang, Liu, Rong and Xu. We also prove that in the asymmetric approximate homomorphism theorem, the bounds exhibit a rather surprising “double phase transition”: the bounds are super-exponential if G G is only assumed to be triangle-free, they become exponential if G G is assumed to have odd girth 7 7 or 9 9 , and become linear if G G has odd girth at least 11 11 . Our proofs use a wide variety of techniques, including entropy arguments, the Frieze–Kannan weak regularity lemma, properties of the generalised Mycielskian construction, and recent work on abundance and the asymmetric removal lemma. 1. Introduction 1.1. Background In this paper, we are concerned with questions of the following type: to what extent can the triangle-freeness of a large graph be “explained” by a small triangle-free graph? To make this vague question more formal, let us recall that a graph G is homomorphic to a graph \Gamma if there exists a function V(G)\to V(\Gamma) which maps edges to edges. Equivalently, G is homomorphic to \Gamma if G is a subgraph of a blowup 1 1 1 A blowup of \Gamma is obtained from \Gamma by replacing every vertex by an independent set, and replacing every edge by a complete bipartite graph. of \Gamma . We write G\to\Gamma if G is homomorphic to \Gamma . Note that if G\to\Gamma and \Gamma is triangle-free, then certainly G is triangle-free as well. If we think of G as large and of \Gamma as small (i.e. of constant size), then the existence of a homomorphism G\to\Gamma gives a constant-sized “explanation” of the triangle-freeness of G . That is, G is a subgraph of a blowup of the constant-sized \Gamma , and this structure already guarantees that G is triangle-free. There are many results which state that under certain conditions, a large triangle-free graph G is homomorphic to a constant-sized triangle-free \Gamma . Perhaps the earliest such result is due to Andrásfai [ 4 ] (see also [ 3 ] ), who proved that if G is a triangle-free graph with minimum degree greater than \frac{2}{5}\lvert G\rvert , then G is bipartite, i.e. homomorphic to K_{2} . The constant \frac{2}{5} is tight in this result, as shown by the five-cycle C_{5} as well as all of its balanced blowups. Extending Andrásfai’s theorem, Häggkvist [ 19 ] proved that if G is a triangle-free graph with minimum degree greater than \frac{3}{8}\lvert G\rvert , then G is homomorphic to C_{5} . The constant \frac{3}{8} is again best possible, as shown by the 8 -vertex Möbius ladder M_{8} , obtained by adding the four long diagonals to C_{8} , as well as all of its balanced blowups. That is, above minimum degree \frac{2}{5} , there is only one triangle-free structure, given by the graph K_{2} . At the threshold \frac{2}{5} , another structure appears, namely that of C_{5} . These are the only two structures above the threshold \frac{3}{8} , at which point a new structure M_{8} appears. Such a pattern continues for a while, and Jin [ 24 ] determined the next seven thresholds as well as the structures that appear in them. However, as proved by Hajnal (quoted in [ 9 ] ), this pattern cannot continue forever. Indeed, Hajnal constructed a family of triangle-free graphs G with minimum degree (\frac{1}{3}-o(1))\lvert G\rvert whose chromatic number tends to infinity. In particular, this implies that these graphs G cannot be homomorphic to any constant-sized triangle-free graph. Rather remarkably, Łuczak [ 37 ] (extending work of Thomassen [ 35 ] ) proved that the constant \frac{1}{3} is best possible, in the following sense. Theorem 1.1 (Łuczak [ 37 ] ) . For every \delta>0 , there exists a triangle-free graph \Gamma such that every triangle-free graph G with minimum degree at least (\frac{1}{3}+\delta)\lvert G\rvert is homomorphic to \Gamma . More recently, Brandt and Thomassé [ 5 ] gave a complete description of the family of all such graphs \Gamma ; they are the so-called Vega graphs . While the results of Andrásfai, Häggkvist, Jin, Łuczak, Brandt–Thomassé and many others are beautiful, they are too rigid to be useful in certain applications. We would often like to assume less about the graph G , and are willing to obtain less precise structural information. For example, a less restrictive notion than that discussed above is that of approximate homomorphisms . Given two graphs G,\Gamma , a function V(G)\to V(\Gamma) is said to be an \varepsilon -approximate homomorphism if it maps all but at most \varepsilon\lvert G\rvert^{2} edges of G to edges of \Gamma . Equivalently, G has an \varepsilon -approximate homomorphism into \Gamma if it is \varepsilon -close 2 2 2 Two n -vertex graphs G_{1},G_{2} on the same vertex set are \varepsilon -close if one can be obtained from the other by adding/deleting at most \varepsilon n^{2} edges, and they are \varepsilon -far otherwise. to a graph homomorphic to \Gamma . The remarkable approximate homomorphism theorem , perhaps first explicitly observed by Tao [ 34 ] , states that every triangle-free graph G has an \varepsilon -approximate homomorphism to a triangle-free graph \Gamma , whose size depends only on \varepsilon . In other words, up to some small noise, every large triangle-free graph G can be obtained from a constant-sized triangle-free graph \Gamma by blowing it up and then passing to a subgraph, where the constant size of \Gamma depends only on the amount of noise, and not on the size of G . Moreover, the approximate homomorphism theorem holds much more generally, dealing not just with triangle-free graphs. To state it in full generality, let us say that a graph \Gamma is F -hom-free if there is