The common-bound conjecture for P-stable degree-sequence families

Let D\mathbb{D} be a P-stable family of degree sequences, or a P-stable simple region, and let (D)\partial(D) denote the boundary of a graphic degree sequence DDD\in\mathbb{D}. Let D|D| denote the size of DD. Common-bound conjecture. There is a polynomial p(n)p^*(n) such that, for each such P-stable family D\mathbb{D}, or just for each P-stable simple region D\mathbb{D},

(D)p(D)\partial(D)\le p^*(|D|)

for all but finitely many graphic DDD\in\mathbb{D}. The conjecture proposes a uniform polynomial bound on the boundary quantity for P-stable regions; the surrounding discussion notes empirical evidence for the candidate polynomial p0(n)=n10p_0(n)=n^{10}, but does not establish the conjecture.

Sources & referencesView supporting material

Primary source

Péter L. Erdős, István Miklós and Lajos Soukup, “Fully graphic degree sequences and P-stable degree sequences”, arXiv:2405.12013 (2024).

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.