The duad-syntheme-total construction for higher values of $n$

324 Views Asked by At

Let $X=\{1,\cdots,2n\}$. Call a $2$-subset of $X$ a duad. Let $D$ be the collection of all $X$'s duads. Call a partition of $X$ into duads a syntheme. Call a partition of $D$ into (necessarily $2n-1$) synthemes a "synthematical total," or simply total for short.

So for example with $n=2$, $\{1,2\}$ would be a duad, $\{\{1,2\},\{3,4\}\}$ a syntheme and $$\{~\{\{1,2\},\{3,4\}\},~\{\{1,3\},\{2,4\}\},~\{\{1,4\},\{2,3\}\}~\}$$ is the only synthematic total for $n=2$, and includes all of the synthemes. Note the action of $S_4$ on this total gives us the exceptional homomorphism $S_4\to S_3$. In general, $S_{2n}$ acts transitively on the set of synthemes with point-stabilizer an internal wreath product $\mathbb{Z}_2\wr S_n$, which means the number of synthemes will be $(2n)!/(2^n n!)$.

Question I. What is the number $t(n)$ of synthematic totals as a function of $n$?

(The terms duad, syntheme and total come from Sylvester IIRC.)

We see $t(1)=1$ and $t(2)=1$ by inspection. One can derive $t(3)=6$ with some geometric reasoning; see John Baez's webpage write-up or Peter Cameron's blog post. The story behind $t(3)=6$ is that of the construction of the (unique) outer automorphism of $S_6$. (The action of $S_6$ induces an action on the set of $6$ totals, which as an automorphism $S_6\to S_6$ is outer.) So:

Question II: How does $S_{2n}$ act on the set of totals?

Recall every $G$-set is a disjoint union of orbits, and the isomorphism type (as a $G$-set) of an orbit is determined by the conjugacy class of its point-stabilizers, which allows us to completely (if abstractly) characterize a group action.

The $n=3$ case also gives rise to the so-called Tutte-Coxeter graph, so:

Bonus question I: Do higher values of $n$ yield additional exotic incidence structures?

And might as well stick this in:

Bonus question II: Does anything similarly interesting happen with $k$-subsets for $k>2$?


In the case of $n=4$, one of the orbits is in bijection with the set of distinct Fano planes.

Under the regular representation of $\mathbb{Z}_2^3$, each vector induces a translation map which, as a permutation of the underlying set is a product of four $2$-cycles or equivalently a syntheme. The set of vectors thus corresponds to a set of synthemes which happens to be a synthematic total.

The totals that can be achieved in this way correspond to the conjugacy class of this copy of $\mathbb{F}_2^3$ sitting inside $S_8$. In this orbit, the stabilizer will be the normalizer inside $S_8$, which will be the affine group $\mathrm{Aff}(3,2)=\mathbb{F}_2^3\rtimes\mathrm{GL}(2,3)$. If we pick an element of $\{1,\cdots,8\}$ to be the "origin," we have an isomorphism of $S_7$-sets

$$ S_8/\mathrm{Aff}(2,3)\cong S_7/\mathrm{GL}(2,3) $$

since $S_8$ is the knit product (aka Zappa–Szép product) of $S_7$ and the internal copy of $\mathbb{F}_2^3$.

pjs36 in the comments raises the question if $S_{2n}$ always acts transitively on the set of synthematic totals. Unfortunately, I can't think of a good reason for that to be the case.

1

There are 1 best solutions below

1
On BEST ANSWER

It turns out this problem is fairly well-studied, under a different guise: 1-factorizations of the complete graph with $2n$ nodes, and a few entries are given in OEIS A000438:

1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040

for $n = 1, 2, \ldots$. It seems to be a hard enough problem that no formula is known.

Isomorphism classes of these $1$-factorizations have also been enumerated for small values of $n$, but again no formula seems to be known. Here are the terms from OEIS A000474, for the same values of $n$:

1, 1, 1, 6, 396, 526915620, 1132835421602062347

I was not aware of this aspect of the problem. I only found it by generating all $6{,}240$ synthematic totals for $n = 4$, and searching OEIS!

One further note, which I'll introduce by copying from the Wikipedia page on graph factorization:

A perfect pair from a 1-factorization is a pair of 1-factors whose union induces a Hamiltonian cycle.

A perfect 1-factorization (P1F) of a graph is a 1-factorization having the property that every pair of 1-factors is a perfect pair. A perfect 1-factorization should not be confused with a perfect matching (also called a 1-factor).

That is (mixing notation), a perfect 1-factorization is one in which the union of any pair of synthemes forms a cycle. According to the page, it is currently only a conjecture that $K_{2n}$ has a perfect 1-factorization for all $n$.


Since I have them, I might as well list the isomorphism types, as well as their orbit sizes and stabilizer sizes, when $S_{8}$ acts on the underlying set $\{1,2, \ldots, 8\}$.

Here's a table on isomorphism classes, in ascending order of orbit size:

\begin{array}{c|c|c|c|c|c|c} \text{orbit size} & 30 & 420 & 630 & 960 & 1680 & 2520 \\ \hline \text{stabilizer size} & 1344 & 96 & 64 & 42 & 24 & 16 \end{array}

The stabilizers are, respectively:

And, everyone's favorite thing, pictures! Below are representatives from each orbit (in the same order as the table above), as well as a depiction of the total. I've tried to display as many symmetries of the total as possible, in each depiction -- I'm quite happy with several of them (notably the septagon, which immediately suggests a generalization for all values of $n$).

 Stabilizer size 1344:
 {{2, 5}, {4, 7}, {8, 3}, {1, 6}}
 {{3, 7}, {8, 4}, {1, 5}, {2, 6}}
 {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 5}, {8, 2}, {4, 6}, {1, 7}}
 {{2, 3}, {8, 5}, {6, 7}, {1, 4}}
 {{1, 3}, {2, 4}, {5, 7}, {8, 6}}

1344 symmetries

 Stabilizer size 96
 {{1, 7}, {4, 6}, {2, 5}, {8, 3}}
 {{2, 3}, {8, 5}, {1, 6}, {4, 7}}
 {{2, 4}, {8, 7}, {1, 5}, {3, 6}}
 {{1, 3}, {5, 6}, {8, 4}, {2, 7}}
 {{5, 7}, {3, 4}, {2, 6}, {8, 1}}
 {{8, 6}, {1, 2}, {3, 7}, {4, 5}}
 {{8, 2}, {6, 7}, {3, 5}, {1, 4}}

96 automorphisms

 Stabilizer size 64:
 {{2, 4}, {8, 6}, {1, 5}, {3, 7}}
 {{2, 5}, {4, 7}, {8, 3}, {1, 6}}
 {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 5}, {8, 2}, {4, 6}, {1, 7}}
 {{2, 3}, {8, 5}, {6, 7}, {1, 4}}
 {{1, 3}, {5, 7}, {2, 6}, {8, 4}}

64 automorphisms

 Stabilizer size 42:
 {{1, 7}, {2, 6}, {3, 5}, {8, 4}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 4}, {1, 6}, {2, 5}, {8, 7}}
 {{2, 4}, {1, 5}, {6, 7}, {8, 3}}
 {{5, 7}, {8, 6}, {2, 3}, {1, 4}}
 {{1, 2}, {3, 7}, {8, 5}, {4, 6}}
 {{1, 3}, {5, 6}, {8, 2}, {4, 7}}

42 automorphisms

 Stabilizer size 24:
 {{1, 7}, {2, 6}, {3, 5}, {8, 4}}
 {{5, 7}, {8, 6}, {2, 3}, {1, 4}}
 {{3, 4}, {1, 6}, {2, 5}, {8, 7}}
 {{8, 2}, {1, 5}, {4, 6}, {3, 7}}
 {{1, 3}, {2, 4}, {8, 5}, {6, 7}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{4, 7}, {5, 6}, {8, 3}, {1, 2}}

24 automorphisms

 Stabilizer size 16:
 (cube)                               (octagon)
 {{5, 6}, {8, 2}, {3, 4}, {1, 7}}     {{2, 3}, {8, 1}, {6, 7}, {4, 5}}
 {{1, 3}, {2, 4}, {5, 7}, {8, 6}}     {{1, 5}, {2, 7}, {8, 4}, {3, 6}}
 {{6, 7}, {2, 5}, {8, 3}, {1, 4}}     {{1, 3}, {5, 7}, {8, 2}, {4, 6}}
 {{3, 7}, {8, 4}, {1, 5}, {2, 6}}     {{2, 6}, {1, 4}, {8, 5}, {3, 7}}
 {{1, 2}, {3, 5}, {4, 6}, {8, 7}}     {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}     {{2, 4}, {1, 7}, {3, 5}, {8, 6}}
 {{2, 3}, {8, 5}, {1, 6}, {4, 7}}     {{2, 5}, {4, 7}, {8, 3}, {1, 6}}

16 automorphisms