ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let HH be a kk-graph with mm edges. For fixed parameters satisfying 2≤k≤r2\le k\le r, with k>3k>3 or r>2r>2, let an rr-cut be a partition of the vertex set into rr parts, and let its size be the number of edges having a vertex in every part. Let S(k,r)S(k,r) denote the Stirling number of the second kind.

Two-thirds excess conjecture. Every kk-graph has an rr-cut of size

S(k,r)r!rkm+Ω\originalleft(m2/3\aftergroup\originalright).\frac{S(k,r)r!}{r^k}m+\Omega\mathopen{}\mathclose\bgroup\originalleft(m^{2/3}\aftergroup\egroup\originalright).

The paper proves a lower bound with exponent 5/95/9 and constructs examples with excess O\originalleft(m2/3\aftergroup\originalright)O\mathopen{}\mathclose\bgroup\originalleft(m^{2/3}\aftergroup\egroup\originalright), so this conjecture would close the gap between the two bounds. The parameter range and quantifiers are reproduced as stated in the source.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.