Balanced even cycles in signed graphs:Turán bounds, double covers, and parity obstructions

Source 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})=\left(\frac{\sqrt2}{2}+o(1)\right)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.