ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For an integer t≥1t\ge 1 and integers m1,m2,…,mt≥3m_1,m_2,\dots,m_t\ge 3, let

F=Cm1+Cm2+⋯+CmtF=C_{m_1}+C_{m_2}+\cdots+C_{m_t}

denote the vertex-disjoint union of cycles of lengths m1,…,mtm_1,\dots,m_t, a 22-regular graph on n=m1+m2+⋯+mtn=m_1+m_2+\cdots+m_t vertices. Write OP(m1,m2,…,mt)OP(m_1,m_2,\dots,m_t) for the following requirement on FF, using exponential notation for repeated table sizes (so that, e.g., OP(53)OP(5^3) means OP(5,5,5)OP(5,5,5)):

  • if nn is odd, the edge set of the complete graph KnK_n can be partitioned into (n−1)/2(n-1)/2 subgraphs, each isomorphic to FF; - if nn is even, the edge set of KnK_n with the edges of a perfect matching removed can be partitioned into (n−2)/2(n-2)/2 subgraphs, each isomorphic to FF.

For each of

OP(32),OP(34),OP(4,5),OP(3,3,5)OP(3^2),\qquad OP(3^4),\qquad OP(4,5),\qquad OP(3,3,5)

no such partition exists. For every choice of t≥1t\ge 1 and m1,…,mt≥3m_1,\dots,m_t\ge 3 other than these four (up to reordering of the mim_i), the required partition exists.

Record

Added
Links

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.