Magic permutations for covering clutters

At least 20 years old · documented by 2005

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.

References

Primary source

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

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A posted construction claims the conjecture is false, but the proposed counterexample has not been independently verified.

Beck formulated the magic permutations conjecture in 2005: realizability of a permutation should be equivalent to an antichain condition on the covering clutter. The general characterization was left open.

Known results

Beck, 2005: the conjecture was verified for $3\times3$ magic squares.
Beck, 2005: it was also verified for $3\times3$ semimagic squares.

Posted attempt

A proposed $d=8$ uniform covering clutter gives three four-element lines that form the required reverse-dominance antichain, while a positive linear identity shows the identity permutation cannot occur in the magic subspace. The construction also supplies a distinct positive labeling with equal line sums, so it claims a complete counterexample; it has not been independently verified.

Current status (as of August 2026): The conjecture is not settled; an unverified construction claims to disprove the general characterization, while the $3\times3$ magic and semimagic cases remain verified.

Sources

export.arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

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.