Balanced even cycles in signed graphs:Turán bounds, double covers, and parity obstructions
Abstract
We study Turán problems for balanced even cycles in simple signed graphs, where signed subgraphs are considered up to switching. For every balanced bipartite signed graph, the signed and ordinary Turán numbers differ by at most a factor of two. Our main structural results concern the underlying graphs that admit a signing in which every 2k-cycle is unbalanced. We characterize these graphs by the absence of an odd dependence among their 2k-cycle incidence vectors, give a cohomological formulation, and construct subgraph-minimal obstructions of arbitrarily large order. In particular, there is no finite forbidden-subgraph characterization. We also give an exact closed-walk criterion for cycles in double covers and derive a direct signed breadth-first-search upper bound. As applications, we prove hex(n,C+4)=(√2/2+o(1))n3/2 and study the signed hexagon number R6(n)=hex(n,{C−3,C+6}). We characterize the underlying graphs counted by R6 and express it as an extremal problem for ordinary C6-free graphs with a prescribed involution. For every sufficiently large n, we construct examples with Ω(n4/3) edges, and we give an equivariant construction attaining the coefficient obtained from the Füredi--Naor--Verstraëte lower bound by double-cover transfer. Finally, we give n-vertex C+10-free signed graphs with Ω(n6/5) edges and use octagon examples to illustrate the limitations of theta-freeness as a signing criterion.
Related
- Spectral and edge conditions for negative Hamiltonian cycles in unbalanced signed graphs
- Sharp Bounds on Torsional Rigidity of Metric Graphs with Signed Delta-Vertex Strengths
- Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
- Commutators of signed n-cycles
- From Balanced Growth to Innovation Cycles:A Solow-Type Semi-Endogenous Growth Model
BibTeX
@misc{wang2026balanced,
title = {{Balanced even cycles in signed graphs:Turán bounds, double covers, and parity obstructions}},
author = {Lujia Wang and Xiaowei Yu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10975},
eprint = {2609.10975},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10975},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Balanced even cycles in signed graphs:Turán bounds, double covers, and parity obstructions
AU - Lujia Wang
AU - Xiaowei Yu
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.10975
UR - https://arxiv.org/abs/2609.10975
AB - We study Turán problems for balanced even cycles in simple signed graphs, where signed subgraphs are considered up to switching. For every balanced bipartite signed graph, the signed and ordinary Turán numbers differ by at most a factor of two. Our main structural results concern the underlying graphs that admit a signing in which every 2k-cycle is unbalanced. We characterize these graphs by the absence of an odd dependence among their 2k-cycle incidence vectors, give a cohomological formulation, and construct subgraph-minimal obstructions of arbitrarily large order. In particular, there is no finite forbidden-subgraph characterization. We also give an exact closed-walk criterion for cycles in double covers and derive a direct signed breadth-first-search upper bound. As applications, we prove hex(n,C_+4)=(√2/2+o(1))n^3/2 and study the signed hexagon number R_6(n)=hex(n,{C_−3,C_+6}). We characterize the underlying graphs counted by R_6 and express it as an extremal problem for ordinary C_6-free graphs with a prescribed involution. For every sufficiently large n, we construct examples with Ω(n^4/3) edges, and we give an equivariant construction attaining the coefficient obtained from the Füredi--Naor--Verstraëte lower bound by double-cover transfer. Finally, we give n-vertex C_+10-free signed graphs with Ω(n^6/5) edges and use octagon examples to illustrate the limitations of theta-freeness as a signing criterion.
ER -