Tight bound characterisation of φ(x,y)
Informal Conjecture (Introduction) — analogue of Kneser's theorem · arXiv:1902.10878
Status open high confidence
The conjecture asks whether $\phi(x,y)$ is always of the form $(\lceil kx \rceil + \lceil ky \rceil - 1)/k$ for some positive integer $k$, as an analogue of Kneser's theorem from additive group theory. The source paper itself notes that the stronger 'wild conjecture' (that the upper bound in Theorem 1.3 is always tight) is false, and leaves the correct characterisation of $\phi(x,y)$ open. A follow-up preprint by Hompe (arXiv:1908.07453) extending threshold computations for $\phi$ was withdrawn and incorporated into the source paper. No subsequent paper resolving or substantially advancing this specific conjecture has been found.
Reviewer notes. The only follow-up paper found (arXiv:1908.07453, Hompe 2019) was withdrawn by its author and folded into the source paper; it extends threshold computations for specific values of $\phi$ but does not address the general characterisation conjecture. The Princeton DataSpace entry 'The girth of digraphs and concatenating bipartite graphs' (dsp01h415pd397) could not be retrieved (HTTP 401). No resolution found in indexed literature.
Context
The authors were motivated by Kneser's theorem from additive group theory and originally entertained a 'wild conjecture' that the upper bound in 1.3 is always tight. This conjecture is stated to be false, but the authors suggest that something like it may still be true, leaving the correct characterisation of $\phi(x,y)$ open.
Notes. The 'wild conjecture' itself is explicitly stated to be false; only the informal residual belief 'maybe something like it is true' survives as an open direction. PDF source — math notation garbled in extraction (e.g. the formula for 1.3 reads as '⌈kx⌉ + 1 ⌉ − ky⌈ k' in the raw text).
Source paper
Concatenating bipartite graphs
Maria Chudnovsky, Patrick Hompe, Alex Scott, Paul Seymour, Sophie Spirkl · 2020-12-07
https://arxiv.org/abs/1902.10878
PDF source