MathDB

The Odd Alternating Cycle Conjecture

Let F\mathbb{F} be a field. For a directed graph GG on nn vertices, its minrank over F\mathbb{F}, denoted by minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G), is the minimum rank over F\mathbb{F} of a matrix representing GG. An alternating odd cycle is a directed graph whose underlying undirected graph is an odd cycle and whose edge orientations alternate, with one exception.

Odd Alternating Cycle Conjecture. For every field F\mathbb{F} there exist ε>0\varepsilon>0 and an odd integer ℓ\ell such that every nn-vertex directed graph GG with

minrk⁡F(G)≤ε⋅n\operatorname{minrk}_{\mathbb{F}}(G)\leq\varepsilon\cdot n

contains an alternating cycle of length ℓ\ell.

The conjecture was proposed in connection with circuit-complexity questions and Valiant's approach to circuit lower bounds. It was disproved over the real field, while its status over finite fields remained open in the source context.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The Odd Alternating Cycle Conjecture

    Let F\mathbb{F} be a field. A digraph is an alternating odd cycle if its underlying undirected graph is a cycle and the orientations of its edges alternate with one exception. For a digraph GG, let minrk⁡F(G)\operatorname{minrk}_{\mathbb{F}}(G) denote its minrank over F\mathbb{F}. Odd Alternating Cycle Conjecture. For every field F\mathbb{F} there exist ε>0\varepsilon>0 and an odd integer ℓ\ell such that every nn-vertex digraph GG with

    minrk⁡F(G)≤ε⋅n\operatorname{minrk}_{\mathbb{F}}(G)\leq\varepsilon\cdot n

    contains an alternating cycle of length ℓ\ell. This conjecture arose from the matrix-rigidity approach to proving superlinear circuit lower bounds; Codenotti, Pudlák, and Resta showed that it would imply superlinear rigidity for certain explicit circulant matrices. Its resolution is not specified here.

    source: Ishay Haviv, “On Minrank and Forbidden Subgraphs”, arXiv:1806.00638 (2018).

Sources & referencesView supporting material

Primary source

Alexander Golovnev and Ishay Haviv, “The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications”, arXiv:2002.08580 (2021).

circuit-complexitygraph-theorymatrix-rigidityminrank

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.