Magic permutations for covering clutters

From papers

Let $([d],\mathcal{L})$ be a covering clutter, let $s$ be its magic subspace, and let a magic permutation be a permutation of $[d]$ realizable by a positive point in $s$ . For a permutation $\sigma$ of $[d]$ , define the reverse dominance order on $\mathcal{P}([d])$ by declaring $L \preccurlyeq_\sigma L'$ when, after writing $L$ and $L'$ in decreasing order according to $\sigma$ , their cardinalities and corresponding indices satisfy the inequalities in the definition above. Magic permutations conjecture. A permutation $\sigma$ of $[d]$ is realizable by a positive point in the magic subspace $s$ of the covering clutter $([d],\mathcal{L})$ if and only if $\mathcal{L}$ is an antichain in the reverse dominance order due to $\sigma$ . The archetype is magic squares; the conjecture was verified for $3\times 3$ magic and semimagic squares, while the general characterization remains open.

Progress summary

Open

The conjecture remains open: only special small examples are known, and no verified proof or counterexample has appeared.

Matthias Beck formulated the magic permutations conjecture in 2005. It proposes that the permutations realizable by positive labelings of a covering clutter are exactly those for which the clutter is an antichain in the associated reverse dominance order.

Known results

For $3\times3$ magic squares, exactly $16$ magic permutations are known (Beck, 2005).
For $3\times3$ semimagic squares, exactly $1296$ permutations are known, matching the conjecture's prediction (Beck, 2005).

Current status (as of August 2026): The general covering-clutter characterization remains conjectural; verification is recorded only for the $3\times3$ magic and semimagic cases.

Sources

export.arxiv.org

Sources & referencesView supporting material

Primary source

Matthias Beck and Thomas Zaslavsky, “An Enumerative Geometry for Magic and Magilatin Labellings”, arXiv:math/0506315 (2005).

1 week ago

The conjecture is false even for a uniform covering clutter that possesses a strongly magic labeling.

Take $d=8$ , $\sigma=(1,2,3,4,5,6,7,8)$ , and the three four-element lines

A=\{1,2,7,8\},\qquad B=\{1,3,4,7\},\qquad C=\{3,4,5,6\}.

They cover $[8]$ , and, having equal cardinality, form a covering clutter. Their elements in decreasing $\sigma$ -order are

(8,7,2,1),\qquad (7,4,3,1),\qquad(6,5,4,3).

These three tuples are pairwise incomparable coordinatewise: $A,B$ differ in opposite directions at their first and third entries; $A,C$ likewise; and $B,C$ differ in opposite directions at their first and second entries. Thus the three lines form an antichain in the required reverse-dominance order.

Write

\ell_D(x)=\sum_{i\in D}x_i.

If the identity permutation were realizable in the magic subspace, there would exist

0<x_1<x_2<\cdots<x_8

with

\ell_A(x)=\ell_B(x)=\ell_C(x).

But these equalities imply

\begin{aligned} 0&=\ell_A(x)+\ell_C(x)-2\ell_B(x)\\ &=(x_2-x_1)+(x_5-x_3) +(x_6-x_4)+(x_8-x_7)>0, \end{aligned}

a contradiction.

The example is nondegenerate: the pairwise-distinct positive labeling

x=(1,2,3,6,4,5,8,7)

satisfies

\ell_A(x)=\ell_B(x)=\ell_C(x)=18.

Hence the clutter does admit strongly magic labelings, but its identity permutation is not realizable despite satisfying the antichain criterion.

0 endorsements

Shivam Patel · 1 day ago