Brubach–Sankararaman–Srinivasan–Xu sampling conjecture for hypergraph matchings
Let be a hypergraph, let be edge weights, and let be a fractional matching, meaning that
where . Brubach–Sankararaman–Srinivasan–Xu conjecture. It is possible to efficiently sample a matching from a distribution such that every edge satisfies
This is a distributional and algorithmic strengthening of the Füredi–Kahn–Seymour guarantee. The source describes related weaker bounds and states that the conjecture remains unresolved.
References
- Georg Anegg, Haris Angelidakis and Rico Zenklusen, “Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture”, arXiv:2009.00697 (2020).
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.