Day–Falgas-Ravry–Treglown multigraph extremal product conjecture

For positive integers aa and rr, let dd satisfy 0da10\le d\le a-1. For a multigraph GG, write P(G)P(G) for its product of edge multiplicities, and let exΠ(n,s,q)ex_\Pi(n,s,q) denote the maximum possible value of P(G)P(G) over multigraphs on nn vertices with no submultigraph on ss vertices having edge-multiplicity sum exceeding qq. Let Tr,d(a,n)\mathcal{T}_{r,d}(a,n) be the family of multigraphs whose vertices admit a partition into rr parts, with multiplicities ada-d within the first part, aa within each other part, and a+1a+1 between distinct parts; define

Σr,d(a,n):=max{e(G):GTr,d(a,n)},{\Sigma}_{r,d}(a,n):=\max\left\lbrace e(G):G\in\mathcal{T}_{r,d}(a,n)\right\rbrace,

and

Πr,d(a,n):=max{P(G):GTr,d(a,n)}.\Pi_{r,d}(a,n):=\max\left\lbrace P(G):G\in\mathcal{T}_{r,d}(a,n)\right\rbrace.

Day–Falgas-Ravry–Treglown conjecture. For all integers a,r,s,da,r,s,d with a,r1a,r\geq 1, d[0,a1]d\in[0,a-1], s(r1)(d+1)+2s\geq(r-1)(d+1)+2, and all sufficiently large nn,

exΠ(n,s,Σr,d(a,s))=Πr,d(a,n).ex_\Pi(n,s,{\Sigma}_{r,d}(a,s))=\Pi_{r,d}(a,n).

This conjecture proposes that, in the stated parameter range, the multigraphs in the construction Tr,d(a,n)\mathcal{T}_{r,d}(a,n) maximize the product of edge multiplicities subject to the corresponding local edge-multiplicity constraint. The source gives no resolution, so the conjecture is recorded as open.

Sources & referencesView supporting material

Primary source

Ran Gu and Shuaichao Wang, “On extremal problems on multigraphs”, arXiv:2301.10430 (2023).

Additional references

2 papers in this index state this conjecture (2021–2023). The statement above is taken from the most recent of them; the others are arXiv:2101.03056.

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.