Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.05357 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915656044118016 |
|---|---|
| author | Luchnikov, Anna Wittebol, Jim Zuiddam, Jeroen |
| author_facet | Luchnikov, Anna Wittebol, Jim Zuiddam, Jeroen |
| contents | The Shannon capacity of graphs, introduced by Shannon in 1956 to model zero-error communication, asks for determining the rate of growth of independent sets in strong powers of graphs. Much is still unknown about this parameter, for instance whether it is computable. Recent work has established a dual characterization of the Shannon capacity in terms of the asymptotic spectrum of graphs. A core step in this duality theory is to shift focus from Shannon capacity itself to studying the asymptotic relations between graphs, that is, the asymptotic cohomomorphisms. Towards understanding the structure of Shannon capacity, we study the "combinatorial complexity" of asymptotic cohomomorphism. As our main result, we prove that the asymptotic cohomomorphism order is universal for all countable preorders. That is, we prove that any countable preorder can be order-embedded into the asymptotic cohomomorphism order (i.e. appears as a suborder). Previously this was only known for (non-asymptotic) cohomomorphism. Our proof is based on techniques from asymptotic spectrum duality and convex structure of the asymptotic spectrum of graphs. Our approach in fact leads to a new proof of the universality of (non-asymptotic) cohomomorphism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_05357 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Universality of asymptotic graph homomorphism Luchnikov, Anna Wittebol, Jim Zuiddam, Jeroen Combinatorics Discrete Mathematics Information Theory 05C69, 05C60, 05C76, 16Y60, 06A07 The Shannon capacity of graphs, introduced by Shannon in 1956 to model zero-error communication, asks for determining the rate of growth of independent sets in strong powers of graphs. Much is still unknown about this parameter, for instance whether it is computable. Recent work has established a dual characterization of the Shannon capacity in terms of the asymptotic spectrum of graphs. A core step in this duality theory is to shift focus from Shannon capacity itself to studying the asymptotic relations between graphs, that is, the asymptotic cohomomorphisms. Towards understanding the structure of Shannon capacity, we study the "combinatorial complexity" of asymptotic cohomomorphism. As our main result, we prove that the asymptotic cohomomorphism order is universal for all countable preorders. That is, we prove that any countable preorder can be order-embedded into the asymptotic cohomomorphism order (i.e. appears as a suborder). Previously this was only known for (non-asymptotic) cohomomorphism. Our proof is based on techniques from asymptotic spectrum duality and convex structure of the asymptotic spectrum of graphs. Our approach in fact leads to a new proof of the universality of (non-asymptotic) cohomomorphism. |
| title | Universality of asymptotic graph homomorphism |
| topic | Combinatorics Discrete Mathematics Information Theory 05C69, 05C60, 05C76, 16Y60, 06A07 |
| url | https://arxiv.org/abs/2512.05357 |