Covering a symmetric crossing supermodular function with hyperedges of prescribed size

Definitions and mathematical statement

Let $V$ be finite and let $p:2^V\to\mathbb R$ be symmetric, meaning $p(X)=p(V\setminus X)$. Assume crossing supermodularity: $p(X)+p(Y)\le p(X\cap Y)+p(X\cup Y)$ whenever all four regions determined by $X,Y$ are nonempty. Specify positive integers $n_1,\ldots,n_k$.

Seek a criterion for the existence of an indexed hyperedge family $H_1,\ldots,H_k\subseteq V$ satisfying \[ |H_i|=n_i\quad(1\le i\le k),\qquad |\{i:H_i\cap X\ne\varnothing,\ H_i\setminus X\ne\varnothing\}| \ge p(X)\quad(X\subseteq V). \] Each hyperedge meeting both sides of a cut contributes one unit, irrespective of how many of its vertices lie on either side. Repeated hyperedges are permitted and count with their indices.

This is a feasibility characterization problem, not the assertion that every input is feasible. For example, $n_i>|V|$, a positive demand at $\varnothing$, or an excessive cut demand makes realization impossible. The result should provide sufficient as well as necessary conditions on the prescribed sizes and demands. The sizes can differ; treating only the equal-size case leaves the main additional difficulty. The convention on cut contribution is essential: counting separated vertex pairs of a hyperedge would define a different covering problem.

Short English statement

Characterize which symmetric crossing-supermodular cut demands can be realized by a hypergraph with a prescribed list of hyperedge sizes.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000023 (AMR-029-0023), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Covering a symmetric crossing supermodular function with hyperedges of prescribed size. Original source indexed by AMR-029-0023. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Covering a symmetric crossing supermodular function with hyperedges of prescribed size. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Covering_a_symmetric_crossing_supermodular_function_with_hyperedges_of_prescribed_size.