Polynomial hitting-number conjecture for complete regular matroids

About 13 years old · traced to

Let MM be a complete regular matroid of rank rr. Here, complete means that a totally unimodular representation of MM is maximally totally unimodular: adding any column that is not a multiple of an existing column violates total unimodularity. Let h(M)h(M) denote the hitting number of MM.

Polynomial hitting-number conjecture. The quantity h(M)h(M) is bounded by a polynomial in rr.

This conjecture asks for a polynomial bound on the hitting number for complete regular matroids, bypassing the decomposition of regular matroids into 11-, 22-, and 33-sums. The source does not state whether the conjecture is known or open; in particular, the analogous bound for 33-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

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.