Equality conjecture for balanced bipartite biindependence in hypercubes

Let QrQ_r be the rr-dimensional hypercube, let αbal(Qr)\alpha_{\text{bal}}(Q_r) denote the maximum total size of a balanced bipartite biindependent pair in QrQ_r, and let a(r)a(r) be the quantity defined in the preceding construction. Equality conjecture. Equality

αbal(Qr)=a(r1)\alpha_{\text{bal}}(Q_r)=a(r-1)

holds for all r1r\geq 1. The preceding construction establishes the lower bound αbal(Qr)a(r1)\alpha_{\text{bal}}(Q_r)\geq a(r-1); the conjecture asserts that this bound is always tight.

Sources & referencesView supporting material

Primary source

Monique Laurent, Sven Polak and Luis Felipe Vargas, “Semidefinite approximations for bicliques and biindependent pairs”, arXiv:2302.08886 (2024).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2212.09861.

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.