Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Romain Bourneuf; Raphael Steiner; St\'ephan Thomass\'e; Yuval Wigderson

Matemática y estadísticaCombinatoria y matemática discreta

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Romain Bourneuf, Raphael Steiner, St\'ephan Thomass\'e, Yuval Wigderson

Preprint

En palabras de los autores

We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $δ_{h o m} ({C_{3}, C_{5}}, {C_{3}}) = \frac{1}{9}$ . Equivalently, for every $ε > 0$ , every $n$ -vertex graph of odd girth at least $7$ and minimum degree at least $(1/9 + ε) n$ admits a homomorphism to a triangle-free graph of size bounded by a function of $ε$ , while there exist graphs of odd girth at least $7$ and minimum degree at least $(1/9 - ε) n$ for which no such bounded-size triangle-free homomorphic image exists. More generally, for every $t \geq 3$ , we prove $δ_{h o m} ({C_{3}, C_{5}}, {K_{t}}) = \frac{1}{3 t}$ . In particular, for every proper monotone class $C$ of graphs, the threshold for graphs of odd girth at least $7$ to admit a homomorphism to a bounded-size graph in $C$ is positive. We further extend this phenomenon to arbitrary odd girth: for every $k \geq 2$ and every proper monotone subclass $C$ of the class of graphs of odd girth at least $2 k - 1$ , the threshold for graphs of odd girth at least $2 k + 3$ to admit a homomorphism to a bounded-size graph in $C$ is positive. These results disprove conjectures of Gishboliner, Hurley and Wigderson and exhibit a sharp contrast with the corresponding zero chromatic-threshold results. Our lower-bound constructions are based on high-dimensional Borsuk graphs, while the matching upper bounds use regularity arguments to recover the structure underlying these constructions.

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF

Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Matemática y estadística Combinatoria y matemática discreta 23 de sept de 2026
Simple symmetric Venn diagrams with 17 and 19 curves
We exhibit simple, rotationally symmetric Venn diagrams with 17 curves and with 19 curves: n Jordan curves carried to one another by rotation through 2{\pi}/n, with every one of the 2^n regions present and connected and, since the diagrams are simple, every crossing on exactly two curves.
Chris Dzoba — arXiv
PreprintCódigo disponible
Matemática y estadística Combinatoria y matemática discreta 23 de sept de 2026
Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures
We prove the Aldous--Fill conjecture and the Guiduli--Mohar conjecture, as well as the corresponding conjecture for $d$ -regular graphs of fixed odd degree.
Maryam Abdi, Ebrahim Ghorbani — arXiv
Preprint
Matemática y estadística Combinatoria y matemática discreta 23 de sept de 2026
Lower Bounds for all List-Decodable Deletion Codes
We prove a lower bound of $Ω_{k} (2^{n} t lo g^{1/ t} n / n^{k + k / t})$ on the optimal size of a $t$ -list decodable $k$ -deletion code, giving a $lo g n$ improvement over the previously best known bounds for $2$ -list decodable $2$ -deletion codes [GH21] and providing the first nontrivial lower bound when $t > 2$ or $k > 2$ .
Andrew D. Lin — arXiv
Preprint
Matemática y estadística Combinatoria y matemática discreta 23 de sept de 2026
Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds
In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $Lit (G) \leq ℓ$ has a regular equipartition into excellent sets with $(1 + o_{ϵ \to 0, ℓ} (1)) \cdot ϵ^{- ℓ - 1}$ parts and in the other direction, for every $ℓ \in N_{+}$ , there is an infinite family of graphs, all of Littlestone dimension $ℓ$ , whose equipartitions into good sets must have size at least $(1 + o_{ϵ \to 0, ℓ} (1)) \cdot ϵ^{- ℓ - 1}$ .
Leonardo N. Coregliano, Fernando G. Jeronimo — arXiv
Preprint
Matemática y estadística Combinatoria y matemática discreta 23 de sept de 2026
Minimising the harmonic sum of cycle lengths
We prove this conjecture for all sufficiently large $k$ , by showing the stronger statement that any $n$ -vertex graph $G$ with $e (G) > (k - 1) (n - k + 1)$ and $n \geq 2 k$ satisfies $s (G) \geq \sum_{ℓ = 2}^{k} 1/ (2 ℓ)$ .
Richard Montgomery, Aleksa Milojevi\'c, Alexey Pokrovskiy y 1 más — arXiv
Preprint

Todos los papers nuevos de Combinatoria y matemática discreta

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

Simple symmetric Venn diagrams with 17 and 19 curves

Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures

Lower Bounds for all List-Decodable Deletion Codes

Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

Minimising the harmonic sum of cycle lengths