Polynomial hitting-number conjecture for complete regular matroids
Let be a complete regular matroid of rank . Here, complete means that a totally unimodular representation of is maximally totally unimodular: adding any column that is not a multiple of an existing column violates total unimodularity. Let denote the hitting number of .
Polynomial hitting-number conjecture. The quantity is bounded by a polynomial in .
This conjecture asks for a polynomial bound on the hitting number for complete regular matroids, bypassing the decomposition of regular matroids into -, -, and -sums. The source does not state whether the conjecture is known or open; in particular, the analogous bound for -sums is described as unclear.
References
Primary source
Manuel Aprile, “Extended formulations for matroid polytopes through randomized protocols”, arXiv:2106.12453 (2021).
Additional references
2 papers in this index state this conjecture (2013–2021). The statement above is taken from the most recent of them; the others are arXiv:1309.5724.
Progress summary
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.