{"id":"arxiv/2609.20231","url":"https://arxiv.org/abs/2609.20231","tags":["math.CO","cs.AI"],"score":0,"title":"Self-complementary completions on six vertices","domain":"math.CO","source":"arxiv","authors":["Xinan Dai","Wenhao Deng","Yingdong Shi","Tailin Wu","Yuchen Yang"],"reviews":0,"subject":"math.CO","summary":"Let \\(\\cthreshold(n)\\) be the largest integer \\(q\\) such that every loopless digraph on \\(n\\) vertices with at most \\(q\\) arcs is isomorphic to a spanning subdigraph of a self-complementary digraph of order \\(n\\). We prove that \\(\\cthreshold(6)=7\\). The upper bound is witnessed by \\[ \\bK{3}\\dunion (x\\longrightarrow y\\longrightarrow z), \\] and follows from a direct argument with a self-complementing permutation. We also determine the complete eight-arc obstruction layer: it consists of five isomorphism classes, or three after converse digraphs are identified. All five are arc-minimal. Each…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}