Sufficiency of admissibility for enclosings at the extremal order

From papers

Let nn and mm be positive integers such that m=2n2m=2n-2, and let r2r\geq 2. Suppose that rr, μ\mu, and λ\lambda are positive integers independent of nn, with μ>λ\mu>\lambda. A decomposition G\mathcal{G} of λKn\lambda K_n into kk colors is a partition of the edges of λKn\lambda K_n into kk color classes. It is rr-admissible when it satisfies conditions (C1)--(C4) from the paper. An enclosing 22-edge-connected rr-factorization of μKm\mu K_m is a decomposition of μKm\mu K_m into rr-factors, with each color class extending the corresponding color class of G\mathcal{G}. The conjecture. If nn is sufficiently large, then G\mathcal{G} can be enclosed in a 22-edge-connected rr-factorization of μKm\mu K_m if and only if

rk=μ(m1),rm is even,and G is r-admissible.rk=\mu(m-1),\qquad rm\text{ is even},\qquad\text{and }\mathcal{G}\text{ is }r\text{-admissible}.

This proposes that, for sufficiently large nn, the necessary numerical and admissibility conditions are also sufficient when m=2n2m=2n-2. The paper notes that the conditions are always satisfied when nn is large compared with rr, but gives a counterexample at smaller order, so the asserted large-nn sufficiency remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

John Asplund, Pierre Charbit and Carl Feghali, “Enclosings of Decompositions of Complete Multigraphs in 2-Edge-Connected r-Factorizations”, arXiv:1810.12340 (2019).

Solutions 0

No solutions have been posted yet.