ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let FCGn,cFCG_{n,c} denote the fair cake-cutting graph with parameters nn and cc. A graph is uniformly most reliable for fixed order nn and size mm if its reliability polynomial is at least that of every competing graph for every edge-operational probability p∈[0,1]p\in[0,1]. Fair cake-cutting conjecture. If

n≡0(mod2c),n\equiv 0 \pmod{2c},

then FCGn,cFCG_{n,c} is a uniformly most reliable hamiltonian graph for m=n+cm=n+c. The case m≥n+4m\geq n+4 is described as largely open in the paper, with only some small cases known computationally; this conjecture proposes a family that is optimal under the stated divisibility condition.

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.