The bounded enumeration conjecture for induced cuts

About 3 years old · traced to

For a graph with the parameters and family of cuts defined in Lemma~, let Cind\mathcal{C}^{\mathrm{ind}} denote the corresponding family of induced cuts. Bounded enumeration conjecture. Lemma~ holds with

∣Cind∣≤2O(1/δ).|\mathcal{C}^{\mathrm{ind}}| \leq 2^{O(1/\delta)}.

This conjecture proposes that the family of induced cuts can be bounded independently of the graph size, depending only exponentially on 1/δ1/\delta. The supplied text gives no resolution or further evidence for the conjecture.

References

Primary source

Charlie Carlson, Ewan Davies, Alexandra Kolla and Aditya Potukuchi, “Approximately counting independent sets in dense bipartite graphs via subspace enumeration”, arXiv:2307.09533 (2023).

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.