Baranyai's partition characterisation of (3,6)-tight graphs

Let G=(V,E)G=(V,E) be a graph with at least 44 vertices. A graph is (3,6)(3,6)-tight when E=3V6|E|=3|V|-6 and every vertex subset UU with at least two vertices spans at most 3U63|U|-6 edges. For an edge ee, write (V,S)/e(V,S)/e for the graph obtained by contracting ee. A graph HH is (2,3)(2,3)-tight when E(H)=2V(H)3|E(H)|=2|V(H)|-3 and every vertex subset UU with at least two vertices spans at most 2U32|U|-3 edges.

The partition characterisation conjecture. The graph GG is (3,6)(3,6)-tight if and only if, for every edge eEe\in E, there exists a partition (S1,S2,S3)(S_1,S_2,S_3) of EE such that

Si=Vifor each i{1,2,3},|S_i|=|V|-i\quad\text{for each }i\in\{1,2,3\},

eS1e\in S_1, and each of the graphs

(V,S1S2),(V,S1S3)/e,(V,S2S3{e})/e(V,S_1\cup S_2),\qquad (V,S_1\cup S_3)/e,\qquad (V,S_2\cup S_3\cup\{e\})/e

is (2,3)(2,3)-tight.

This conjecture is proposed as a correction to a claimed combinatorial characterisation of minimal 33-rigidity. The paper presents a counterexample to the earlier characterisation and suggests that the stated partition condition may provide the appropriate characterisation; its resolution is not established here.

Sources & referencesView supporting material

Primary source

Sean Dewar, “A counter-example to Baranyai's combinatorial characterisation for 3-rigidity”, arXiv:2601.19460 (2026).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.