Lau's Extension Theorem

Less than 1 year old · traced to

Let GG be a loopless multigraph, with S,R⊆V(G)S,R\subseteq V(G) such that S∩R=∅S\cap R=\emptyset, SS is QkQk-edge-connected, and every r∈Rr\in R has degree at least QkQk, where Q≥30Q\geq 30. Given a vertex vv and a subpartition Pk(v)P_k(v) of E(v)E(v) into kk parts, an SS-subgraph extends vv when it satisfies the extension condition associated with the subpartition at vv; a collection of subgraphs balances S∪RS\cup R when their induced edge subpartitions are balanced at every vertex in S∪RS\cup R.

Lau's Extension Theorem. There are kk edge-disjoint SS-subgraphs that extend vv and balance S∪RS\cup R if either v∈Sv\in S, d(v)=Qkd(v)=Qk, and Pk(v)P_k(v) is a balanced edge subpartition of E(v)E(v), or N(v)⊆S∪RN(v)\subseteq S\cup R, d(v)≤Qkd(v)\leq Qk, v∉S∪Rv\notin S\cup R, and there is no edge cut of size at most QkQk that breaks GG into C1,C2C_1,C_2 with S⊆C2S\subseteq C_2, v∈C1v\in C_1, and R∩C1≠∅R\cap C_1\neq\emptyset.

The paper states that this theorem was used in Lau's proof of the 30k30k bound for Steiner forest packing, but identifies a mistake in it and provides a counterexample. Thus the asserted theorem is refuted as stated; the paper's corrected argument instead yields a 36k36k bound, improved to 35k35k when k≥8k\geq 8.

References

Primary source

Jinghan A Zeng, “On the Extension Theorem for Packing Steiner Forests”, arXiv:2603.16956 (2026).

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.