# Coloring Groups

Ben Adenbaum
Alexander Wilson

###### Abstract

We introduce coloring groups, which are permutation groups obtained from a
proper edge coloring of a graph. These groups generalize the generalized
toggle groups of Striker (which themselves generalize the toggle groups
introduced by Cameron and Fon-der-Flaass). We present some general results
connecting the structure of a coloring group to the structure of its graph
coloring, providing graph-theoretic characterizations of the centralizer and
primitivity of a coloring group. We apply these results particularly to
generalized toggle groups arising from trees as well as coloring groups
arising from the independence posets introduced by Thomas and Williams.

##  1 Introduction

Cameron and Fon-der-Flaass first introduced toggle groups on order ideals [2]
in order to study the map now known as rowmotion (the name “toggle group” was
introduced later in [10]). Given a poset $P$, each element $p\in P$ has a
corresponding permutation $\tau_{p}$ (called a toggle) of the order ideals
$\mathcal{J}(P)$ of $P$ which acts in the following way, toggling the element
$p$ as long as the result is still an order ideal.

$\displaystyle\tau_{p}(I)$ $\displaystyle=\begin{cases}I\cup\\{p\\}&\text{ if
}p\notin I\text{ and }I\cup\\{p\\}\in\mathcal{J}(P)\\\
I\setminus\\{p\\}&\text{ if }p\in I\text{ and
}I\setminus\\{p\\}\in\mathcal{J}(P)\\\ I&\text{ otherwise}\end{cases}$

To understand properties of rowmotion and associated operations—in particular
their order—Striker introduced generalized toggle groups [9] where the order
ideals of a poset are replaced with an arbitrary set of allowable subsets and
the poset is replaced by just a finite set.

######  Definition 1.1 (Toggle Group).

[9]

Let $E$ be a finite set, and let $L$ be any subset of the power set $2^{E}$.
For each $e\in E$, the toggle $\tau_{e}$ is defined as follows:

$\tau_{e}(X)=\begin{cases}X\cup\\{e\\}&\text{if }e\notin X\text{ and
}X\cup\\{e\\}\in L\\\ X\setminus\\{e\\}&\text{if }e\in X\text{ and
}X\setminus\\{e\\}\in L\\\ X&\text{otherwise}\end{cases}$

The set $\\{\tau_{e}|e\in E\\}$ are the set of toggles. Let $T(L)$ be the
subgroup of $S_{L}$ generated by the toggles.

######  Example 1.2.

Let $E=[4]$ and
$L=\\{\emptyset,\\{1\\},\\{1,2\\},\\{1,2,3\\},\\{1,2,3,4\\},\\{4\\},\\{3,4\\},\\{2,3,4\\}\\}$

  * •

$\tau_{1}=(\emptyset,\\{1\\})(\\{2,3,4\\},\\{1,2,3,4\\})$

  * •

$\tau_{2}=(\\{1\\},\\{1,2\\})(\\{3,4\\},\\{2,3,4\\})$

  * •

$\tau_{3}=(\\{1,2\\},\\{1,2,3\\})(\\{4\\},\\{3,4\\})$

  * •

$\tau_{4}=(\emptyset,\\{4\\})(\\{1,2,3\\},\\{1,2,3,4\\})$

In this case $T_{L}\cong S_{4}\rtimes(C_{2})^{3}$

The idea of order ideal toggling has been generalized from the purely
combinatorial perspective to the piece-wise linear and birational realms in
[3] and [5, 6] respectively. These groups were studied in-depth by Striker in
[9] when arising from some families of combinatorial and geometric objects.
More recently in [1] they have been considered with respect to their group
theoretic properties such as primitivity.

To all generalized toggle groups, there is a natural partial order called the
_toggle poset_ which we denote by $P_{L}$. The cover relations in this poset
are given by $X\lessdot Y$ if $X\subseteq Y$ and there exists some $e\in E$
such that $\tau_{e}(X)=Y$, and $|Y|-|X|=1$. Importantly, each edge of the
Hasse diagram is naturally labeled by the element toggled in for the cover.

######  Example 1.3.

The toggle poset of the generalized toggle group of Example 1.2

$\emptyset$$\\{4\\}$$\\{1\\}$$\\{1,2\\}$$\\{3,4\\}$$\\{2,3,4\\}$$\\{1,2,3\\}$$\\{1,2,3,4\\}$41322341

In this paper, we take inspiration from this edge labeling of the Hasse
diagram to introduce coloring groups, which arise from proper edge colorings
of finite graphs. Coloring groups encompass all finite groups generated by
involutions (in particular the generalized toggle groups). Because our
interest lies in understanding combinatorial objects with natural involution
structure (e.g. toggle groups, or quivers up to mutation), we want to
understand how the structure of the graphs and their edge colorings control
the structure of the corresponding coloring group.

The paper is organized as follows:

  * •

In Section 2 we define coloring groups and characterize which permutation
groups arise as coloring groups.

  * •

In Section 3 we prove general tools for working with coloring groups as well
as more specialized tools in the case that the underlying graph $G$ is a tree.

  * •

In Section 4 we study generalized toggle groups arising from trees as well as
coloring groups arising in the study of independence posets.

  * •

In Appendix A we provide some constructions of the groups $S_{n},A_{n},D_{n},$
and the type-B coxeter group $B_{m}$ as coloring groups.

  * •

Finally, in Appendix B we provide data on the coloring groups arising from
trees of order at most 12.

Acknowledgements: The authors would like to thank Jonathan Bloom and Jessica
Striker for their guidance and many, many helpful conversations. They would
also like to thank Nate Lesnevich for his insights on an early version of this
project.

##  2 Preliminaries and Definitions

In this paper, a graph of order $n$ will be a simple undirected graph on $n$
vertices unless otherwise specified. Given a graph $G$, a proper edge coloring
of $G$ on $k$ colors is a surjective map $\kappa:E(G)\to[k]$ such that for any
two incident edges $e_{1}$ and $e_{2}$, we have that
$\kappa(e_{1})\neq\kappa(e_{2})$. We define the coloring group
$\mathfrak{G}_{\kappa}$ corresponding to $\kappa$ as the subgroup of
$S_{V(G)}\cong S_{n}$ generated by the involutions

$\displaystyle\tau_{a}=\prod_{\begin{subarray}{c}\\{i,j\\}\in E(G)\\\
\kappa(\\{i,j\\})=a\end{subarray}}(i,j)$ (1)

for $a\in[k]$. Note that because the edge coloring is proper, the product can
be taken in any order, and $\tau_{a}$ simply swaps the vertices on either end
of each edge colored $a$.

######  Example 2.1.

The following graph is shown with a proper edge coloring $\kappa:E(G)\to[3]$
where the colors 1, 2, and 3 of the edges are represented by blue, orange, and
green respectively.

$1$$2$$3$$4$$5$$6$$7$

The corresponding coloring group is isomorphic to the general linear group
$GL(3,2)$.

$\displaystyle\mathfrak{G}_{\kappa}=\langle{\color[rgb]{0,0.5234375,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5234375,1}(2,3)(4,5)},{\color[rgb]{1,0.56640625,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.56640625,0}(3,4)(6,7)},{\color[rgb]{0.56640625,0.828125,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.56640625,0.828125,0}(1,2)(3,6)}\rangle\cong
GL(3,2).$

As a subgroup of $S_{n}$, the group $\mathfrak{G}_{\kappa}$ is an example of a
permutation group of degree $n$. Cayley’s theorem tells us that every finite
group is isomorphic to a permutation group, but coloring groups are in a
smaller class of groups which are generated by involutions. Theorem 2.2 shows
that the class of coloring groups is in fact precisely the class of finite
groups generated by involutions.

######  Theorem 2.2.

Let $\mathfrak{G}$ be a finite group generated by involutions. Then there is a
connected graph $G$ with proper edge coloring $\kappa$ such that
$\mathfrak{G}_{\kappa}$ is isomorphic to $\mathfrak{G}$.

###### Proof.

Suppose that $\mathfrak{G}=\langle g_{1},\dots,g_{k}\rangle$ with each $g_{i}$
an involution. Let $G$ be the Cayley graph of $\mathfrak{G}$. If $\\{a,b\\}\in
E(G)$ then $b=ag_{i}$ for a unique generator $g_{i}$, so define
$\kappa(\\{a,b\\})=i$. As the generators are involutions, this edge coloring
is proper. Let $\mathfrak{G}_{\kappa}$ be the corresponding coloring group. We
claim that $\mathfrak{G}_{\kappa}\cong\mathfrak{G}$. To see why, consider
$\mathfrak{G}$ as as a subgroup of $S_{V(G)}$. Note that each $g_{i}$
corresponds to the product of the disjoint transpositions $(a,b)$ such that
$b=ag_{i}$, so $\mathfrak{G}$ is the group generated by these involutions. For
each $i$ under this identification, $g_{i}$ is exactly $\tau_{i}$, so the
groups are equal as permutation groups. ∎

This is a very large class of groups, and the graphs obtained in the proof of
Theorem 2.2 have as many vertices as the group $\mathfrak{G}$ has elements. We
thus restrict ourselves to situations where the graph $G$ and its proper edge
coloring $\kappa$ have nice structure. Of particular interest will be the
symmetry of this coloring, captured in the following definition.

######  Definition 2.3.

For a proper edge coloring $(G,\kappa)$, the group
$\operatorname{Aut}_{\kappa}(G)$ consists of all permutations $\sigma\in
S_{V(G)}$ so that $\\{i,j\\}$ is an edge of $G$ colored $a$ under $\kappa$ if
and only if $\\{\sigma(i),\sigma(j)\\}$ is an edge of $G$ colored $a$ under
$\kappa$.

######  Lemma 2.4.

For a proper edge coloring $(G,\kappa)$, if
$\sigma\in\operatorname{Aut}_{\kappa}(G)$ fixes a vertex $v$, it fixes every
neighbor of $v$.

###### Proof.

Suppose $\sigma\in\operatorname{Aut}_{\kappa}(G)$ fixes $v$ and $w$ is a
neighbor of $v$ connected by an edge colored $a$. Then $\\{v,\sigma(w)\\}$
must be an edge colored $a$. Because $\kappa$ is a proper edge coloring, the
only edge incident to $v$ colored $a$ is the edge $\\{v,w\\}$. Hence
$\sigma(w)=w$. ∎

A permutuation group $\mathfrak{G}$ of degree $n$ acts naturally on the set
partitions of $[n]$. If $\mathfrak{G}$ fixes any nontrivial set partition
$\pi$ (i.e. one not consisting of a single block or all singletons), then we
say that $\mathfrak{G}$ is imprimitive with $\pi$ being a system of
imprimitivity. Otherwise, we say that $\mathfrak{G}$ is primitive.

##  3 Tools for Analyzing Coloring Groups

We begin with some results that can be applied to any coloring group. The
following theorem characterizes the centralizer of a coloring group.

######  Theorem 3.1.

For proper edge coloring $(G,\kappa)$, the centralizer
$C_{S_{V(G)}}(\mathfrak{G}_{\kappa})$ of the corresponding coloring group in
the symmetric group is isomorphic to $\operatorname{Aut}_{\kappa}(G)$.

###### Proof.

Let $\sigma\in C_{S_{V(G)}}(\mathfrak{G}_{\kappa})$ and suppose that
$\\{i,j\\}$ is an edge colored $a$. Then $(i,j)$ is a transposition in
$\tau_{a}$. Because $\sigma$ commutes with $\tau_{a}$,

$\sigma\tau_{a}\sigma^{-1}=\tau_{a}.$

Then $(\sigma(i),\sigma(j))$ is also a transposition in $\tau_{a}$ and hence
$\\{\sigma(i),\sigma(j)\\}$ is an edge of $G$ colored $a$ under $\kappa$.
Hence, $\sigma\in\operatorname{Aut}_{\kappa}(G)$.

Suppose conversely that $\sigma\in\operatorname{Aut}_{\kappa}(G)$. Then for
each color, $\sigma$ induces a permutation $\sigma^{\prime}$ of the edges of
that color. Fixing a color $a$, let
$\\{i_{1},j_{1}\\},\dots,\\{i_{m},j_{m}\\}$ be the edges of that color. Then

$\displaystyle\sigma\tau_{a}\sigma^{-1}$
$\displaystyle=(\sigma(i_{1}),\sigma(j_{1}))\dots(\sigma(i_{m}),\sigma(j_{m}))$
$\displaystyle=(i_{\sigma^{\prime}(1)},j_{\sigma^{\prime}(1)})\dots(i_{\sigma^{\prime}(m)},j_{\sigma^{\prime}(m)})$
$\displaystyle=\tau_{a}$

where the final equality follows from the fact that $\kappa$ is a proper edge
coloring, so these transpositions commute pairwise. Because $\sigma$ commutes
with each generator of $\mathfrak{G}_{\kappa}$, we have that $\sigma\in
C_{S_{V(G)}}(\mathfrak{G}_{\kappa})$ ∎

######  Corollary 3.2.

For a proper edge coloring $(G,\kappa)$,

$\mathfrak{G}_{\kappa}\subseteq C_{S_{V(G)}}(\operatorname{Aut}_{\kappa}(G)).$

In particular, a necessary condition for $\mathfrak{G}_{\kappa}\cong S_{V(G)}$
is that $\operatorname{Aut}_{\kappa}(G)$ is trivial.

The following definition and lemma provide a graph-theoretic characterization
of when a coloring group is primitive via vertex colorings.

######  Definition 3.3.

For a proper edge coloring $(G,\kappa)$, consider a vertex coloring of
$\nu:V(G)\to[\ell]$. The coloring $\nu$ is called imprimitive if the following
two statements hold:

  1. (i)

If an edge colored $b$ connects a vertex colored $a$ to a vertex colored $c$
with $a\neq c$, then every vertex colored $a$ is connected to a vertex colored
$c$ by an edge colored $b$.

  2. (ii)

At least one color appears strictly more than one time and strictly less than
$|G|$ times.

######  Example 3.4.

The following edge coloring of the path graph $P_{15}$ has an imprimitive
vertex coloring.

######  Example 3.5.

The following proper edge coloring has an imprimitive vertex coloring where
the vertices are partitioned into the three sets of four vertices which are on
the same line.

######  Lemma 3.6.

For a proper edge coloring $(G,\kappa)$, the group $\mathfrak{G}_{\kappa}$ is
imprimitive if and only if there exists an imprimitive vertex coloring of $G$
with respect to the edge coloring $\kappa$.

###### Proof.

Given an imprimitive vertex coloring, the set partition obtained by putting
two vertex labels in the same set if and only if the vertices are colored with
the same color is a system of imprimitivity. Conversely, a system of
imprimitivity prescribes the distribution of vertex colors for an imprimitive
vertex coloring. ∎

When considering toggle groups, one of the motivating questions has been
whether elements that mimic coxeter elements, i.e. products of the generating
involutions in some prescribed order, have a predictable order. When we
restrict to the case of forests, we get the following.

######  Lemma 3.7.

Suppose $G$ is a disjoint union of $\ell$ trees with orders given by
$\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{\ell}$. Then for any proper
edge coloring $\kappa:E(G)\to[k]$, the product of all the corresponding
generators

$\tau_{1}\dots\tau_{k}\in\mathfrak{G}_{\kappa}$

in any order has cycle type $\lambda$.

###### Proof.

It suffices to show that in the case that $G$ is a tree of order $n$, the
product of all the transpositions corresponding to edges in $G$ in any order
is an $n$-cycle. The following proof is based on an argument by Darij Grinberg
communicated in a comment on Math Stack
Exchange111https://math.stackexchange.com/questions/2577311/product-of-
transpositions-from-edges-of-a-tree-is-a-cycle-of-length-n.

We proceed by induction on the order of $G$. Let $\tau_{1},\dots,\tau_{n-1}$
be the transpositions corresponding to the $n-1$ edges of $G$ in any order. By
conjugating by a transposition on one end of this sequence, we can cyclically
permute the sequence without changing the cycle structure of the product.
Without loss of generality, assume we have cyclically permuted the
transpositions so that the transposition $\tau_{1}$ appearing first
corresponds to an edge incident to a leaf labeled $x$. By the inductive
hypothesis, $\tau_{2}\tau_{3}\cdots\tau_{n-1}$ is an $n-1$-cycle on
$\\{1,\dots,n\\}\setminus\\{x\\}$. Hence, $\tau_{1}\tau_{2}\dots\tau_{n-1}$ is
an $n$-cycle on $\\{1,\dots,n\\}$. ∎

In particular when $G$ is a tree of order $n$ any such element is an
$n$-cycle, which will be essential for Theorem 3.9 and its consequences.

######  Lemma 3.8.

If $(G,\kappa)$ is a proper edge-coloring of a tree with $n$ vertices that
uses at least 3 colors,

$\left|\mathfrak{G}_{\kappa}\right|\geq\frac{n^{2}}{n-\varphi(n)}$

where $\varphi(n)$ is the Euler totient function.

###### Proof.

Note that if $\sigma_{1}$ and $\sigma_{2}$ are distinct long cycles in $S_{n}$
which generate the same subgroup, then $\sigma_{1}={\sigma_{2}}^{r}$ for some
$1<r<n$. Then because ${\sigma_{2}}^{s}$ has a fixed point if and only if
$n|s$,

$\sigma_{1}(a)={\sigma_{2}}^{r}(a)={\sigma_{2}}^{r-1}(\sigma_{2}(a))\neq{\sigma_{2}}(a).$

Without loss of generality, suppose that $G$ has a leaf labeled $1$ incident
to an edge colored $1$. Then any long cycle of the form

$\displaystyle\sigma=\tau_{1}\tau_{i_{1}}\dots\tau_{i_{k-1}}$

has the property that $\sigma(1)=\tau_{1}(1)$. Because there are at least
three colors there must be at least two colors that don’t commute with each
other. Hence, there are at least two long-cycles $\sigma_{1}$ and $\sigma_{2}$
of this form. Because $\sigma_{1}(1)=\sigma_{2}(1)$, they must generate
distinct subgroups. Then $\mathfrak{G}_{\kappa}$ has a subset
$\langle\sigma_{1}\rangle\langle\sigma_{2}\rangle$ with order

$\left|\langle\sigma_{1}\rangle\langle\sigma_{2}\rangle\right|=\frac{\left|\langle\sigma_{1}\rangle\right|\cdot\left|\langle\sigma_{2}\rangle\right|}{\left|\langle\sigma_{1}\rangle\cap\langle\sigma_{2}\rangle\right|}.$

Note that because $\sigma_{1}$ and $\sigma_{2}$ generate distinct subgroups,
their intersection can only contain elements of the form ${\sigma_{1}}^{m}$
where $m$ is not relatively prime to $n$. Hence
$\left|\langle\sigma_{1}\rangle\cap\langle\sigma_{2}\rangle\right|\leq
n-\varphi(n)$. ∎

The following theorem provides a condition for narrowing down the possible
primitive coloring groups that can arise from a graph $G$.

######  Theorem 3.9.

Let $\kappa:E(G)\to[k]$ be a proper edge coloring of a graph of order $n$ and
suppose that $\mathfrak{G}_{\kappa}$ is primitive. Suppose that restricting to
the edges colored by a subset of $\ell$ colors (and their incident vertices)
forms a tree $T$ of order $m$. If $n-m\geq 3$, then
$A_{n}\leq\mathfrak{G}_{\kappa}$. Furthermore, if we assume that $\ell>2$,
then $A_{n}\leq\mathfrak{G}_{\kappa}$ unless one of the following hold (where
in each case $q$ is a prime power):

  * (i)

$n-m=2$, $n=q+1$, $PGL_{2}(q)\leq\mathfrak{G}_{\kappa}\leq P\Gamma L_{2}(q)$,
or

  * (ii)

$n-m=1$ and either

    * (a)

$n=q^{d}$, $d\geq 1$, $AGL_{d}(q)\leq\mathfrak{G}_{\kappa}\leq A\Gamma
L_{d}(q)$, or

    * (c)

$n=24$, $\mathfrak{G}_{\kappa}=M_{24}$, or

  * (iii)

$n-m=0$ and either

    * (a)

$n=\frac{q^{d}-1}{q-1}$, $d\geq 2$, $PGL_{d}(q)\leq\mathfrak{G}_{\kappa}\leq
P\Gamma L_{d}(q)$, or

    * (b)

$n=23$, $\mathfrak{G}_{\kappa}=M_{23}$.

###### Proof.

Much of the heavy-lifting in this proof is done by noting that the existence
of such a tree $T$ guarantees a cycle in $\mathfrak{G}_{\kappa}$ that fixes
$n-m$ points using Lemma 3.7, and then applying [7, Theorem 1.2]. We need only
rule out the following cases:

  * •

$n-m=1,\;p\geq 5\text{ is prime,}\;n=p+1,\;\mathfrak{G}_{\kappa}=PGL_{2}(p)$
or $\mathfrak{G}_{\kappa}=PSL_{2}(p)$.

The graph contains a subtree of order $p$. Because the coloring group
corresponding to this tree has prime degree, it is primitive and so must fall
under case (iii) of the theorem. If the coloring group corresponding to this
tree were to contain the alternating group or be $M_{23}$, it’s clear that
$PGL_{2}(p)$ and $PSL_{2}(p)$ would be too small to contain it. It must then
be the case that $PGL_{d}(q)\leq\mathfrak{G}_{\kappa}\leq PGL_{2}(p)$ where
$p=\frac{q^{d}-1}{q-1}$ for some $d\geq 2$. This containment implies that the
order of $PGL_{d}(q)$ divides the order of $PGL_{2}(p)$. That is:

$\displaystyle\frac{(q^{d}-1)(q^{d}-1)\cdots(q^{d}-q^{d-1})}{q-1}\mid
p^{3}-p.$

We proceed by showing this is impossible.

By applying Cauchy’s bound to the polynomial
$q^{\binom{d-2}{2}-1}(q^{d}-q)-(q^{d}-1)^{2}$ and noting its positive leading
coefficient, we obtain the inequality

$\displaystyle q^{\binom{d-2}{2}-1}>\frac{(q^{d}-1)^{2}}{q^{d}-q}$ (2)

as long as $q\geq 3,d\geq 3$. From this inequality it is straightforward to
derive that $|PGL_{d}(q)|>|PGL_{2}(p)|$:

$\displaystyle\frac{(q^{d}-1)^{2}}{q^{d}-q}$
$\displaystyle<q^{\binom{d-2}{2}-1}$
$\displaystyle<q^{\binom{d-2}{2}-1}\prod_{i=2}^{d-1}(q^{d-1}-i)$
$\displaystyle=\prod_{i=2}^{d-1}(q^{d}-q^{i})$
$\displaystyle<(q-1)^{2}\prod_{i=2}^{d-1}(q^{d}-q^{i})$
$\displaystyle\frac{(q^{d}-1)^{2}}{(q^{d}-q)^{2}}$
$\displaystyle<\prod_{i=1}^{d-1}(q^{d}-q^{i})$ $\displaystyle p^{3}$
$\displaystyle<p\prod_{i=1}^{d-1}(q^{d}-q^{i})$ $\displaystyle=|PGL_{d}(q)|$

Hence, as long as $q\geq 3$ and $d\geq 3$, we have that
$|PGL_{d}(q)|>p^{3}>p^{3}-p=|PGL_{2}(p)|$ and the above containment is
impossible.

For the case $d=2$, the containment implies that

$\frac{(q^{2}-1)(q^{2}-q)}{q-1}=p(q^{2}-q)\mid p^{3}-p=p(q-2)q.$

This implies that $q-1\mid q-2$, which is impossible for $q>1$.

The final case is when $q=2$ and $d\geq 3$. If Inequality 2 does not hold, it
is straightforward to show that $d\leq 8$. The only values between $3$ and $8$
for which $2^{d}-1$ is prime are $d=3,5,$ or $7$. When $d=3$, we have that
$p=7$, so $\mathfrak{G}_{\kappa}$ must contain $S_{7}$ (See Appendix B). For
$d=5,7$ we have that $|PGL_{d}(q)|>|PGL_{2}(p)|$.

  * •

$n-m=1$, $\mathfrak{G}_{\kappa}=M_{11}$

In this case, the graph contains a subtree of order 10. The orders of coloring
groups generated on a tree of order 10 with at least three colors are
$200,\;240,\;2^{5}\cdot 5!,\;120^{2},$ and $10!$ (see Appendix B). An
enumeration of the subgroups of $M_{11}$ shows that it has no subgroups of
these orders.

  * •

$n-m=1,\;\mathfrak{G}_{\kappa}=M_{12}$

The orders of coloring groups on a tree with 11 vertices with at least three
colors are $\frac{11!}{2}$ or $11!$ (See Appendix B). Both of these orders are
too large to be contained in $M_{12}$.

  * •

$n-m=0$, $\mathfrak{G}_{\kappa}=PSL_{2}(11)$ or
$\mathfrak{G}_{\kappa}=M_{11}$.

See the orders given above for coloring groups on a tree with 11 vertices.

  * •

$n-m=0$, $n=p$, a prime, $C_{p}\leq\mathfrak{G}_{\kappa}\leq AGL_{1}(p)$

Note that $|AGL_{1}(p)|=p(p-1)$, but Lemma 3.8 tells us that a tree on a prime
number of vertices with at least three colors produces a coloring group of
order at least $p^{2}$.

∎

Although we have not ruled out case (iii)b in Theorem 3.9, we have no example
of a tree $G$ which realizes $M_{23}$ as a coloring group, and we conjecture
that no such graph exists. Note that the nonexistence of such a tree would
also rule out case (ii)c.

The following theorem characterizes coloring groups on trees by their
centralizer using Theorem 3.1.

######  Lemma 3.10.

For $(G,\kappa)$ a proper edge coloring of a tree,
$\operatorname{Aut}_{\kappa}(G)$ is either trivial or has order two.

###### Proof.

If $G$ has a unique center, then every automorphism of $G$ must fix this
center. By Lemma 2.4, $\operatorname{Aut}_{\kappa}(G)$ is trivial.

Alternatively, if $G$ has two vertices $v_{1}$ and $v_{2}$ of maximum
eccentricity, a nontrivial automorphism $\varphi$ must swap $v_{1}$ and
$v_{2}$. If $\psi$ were another such automorphism, then $\psi\varphi$ would
fix $v_{1}$ and $v_{2}$, and by Lemma 2.4, $\psi\varphi$ is the trivial
automorphism and $\psi=\varphi^{-1}$. Hence, if
$\operatorname{Aut}_{\kappa}(G)$ is nontrivial, it consists of a single
automorphism of order 2. ∎

######  Theorem 3.11.

For $(G,\kappa)$ a proper edge coloring of a tree, either
$C_{S_{V(G)}}(\mathfrak{G}_{\kappa})$ is trivial, or $|G|=2m$ is even and
$\mathfrak{G}_{\kappa}$ is isomorphic to a subgroup of the type B coxeter
group $B_{m}$.

###### Proof.

If $\operatorname{Aut}_{\kappa}(G)$ is nontrivial and $e$ is the edge between
the two vertices of $G$ of maximum eccentricity. The graph $G\setminus\\{e\\}$
is the disjoint union of two trees $T_{1}$ and $T_{2}$. The nontrivial element
$\varphi\in\operatorname{Aut}_{\kappa}(G)$ restricts to an isomorphism between
$T_{1}$ and $T_{2}$. Let $\kappa_{1}$ be the edge coloring of $T_{1}$ and let
$\kappa^{\prime}$ be the edge coloring of $G$ modified so that the edge $e$
has a unique color $c$. It’s clear that $\mathfrak{G}_{\kappa_{1}}$ is a
subgroup of $\mathfrak{G}_{\kappa^{\prime}}$. Let

$\displaystyle N$
$\displaystyle=\\{g\tau_{c}g^{-1}:g\in\mathfrak{G}_{\kappa^{\prime}}\\}\cup\\{1\\}\subseteq\mathfrak{G}_{\kappa^{\prime}}.$

Then $N$ is a normal subgroup of $\mathfrak{G}_{\kappa^{\prime}}$ isomorphic
to ${C_{2}}^{m}$ where $m$ is the order of $T_{1}$ and
$\mathfrak{G}_{\kappa^{\prime}}=NG_{\kappa_{1}}$. Hence,
$\mathfrak{G}_{\kappa^{\prime}}=N\rtimes G_{\kappa_{1}}$ where
$G_{\kappa_{1}}$ acts on $N$ by permutation, meaning
$\mathfrak{G}_{\kappa^{\prime}}$ can be recognized as the wreath product

$\displaystyle\mathfrak{G}_{\kappa^{\prime}}$ $\displaystyle\cong
C_{2}\omega\mathfrak{G}_{\kappa_{1}}$ $\displaystyle\leq C_{2}\omega S_{m}$
$\displaystyle\cong B_{m}.$

Finally, we have that the original coloring group
$\mathfrak{G}_{\kappa}\subseteq\mathfrak{G}_{\kappa^{\prime}}$. ∎

######  Example 3.12.

The following tree has a color-preserving automorphism that reflects the graph
horizontally. The labels are taken from $\\{-6,\dots,-1,1,\dots,6\\}$ to show
how the corresponding coloring group embeds in the group $B_{6}$ of signed
permutations.

-6-5-4-3-2-1123456

Finally, we provide a sufficient condition for a coloring group on a tree of
order $n$ to be isomorphic to the symmetric group $S_{n}$.

######  Definition 3.13.

Let $G$ be a graph with proper edge coloring $\kappa:E(G)\to[k]$. Let $e$ be
an edge such that every edge incident to $e$ is of a distinct color. We call
$e$ a symmetric edge if there exists a subset $S$ of $[k]$ containing the
colors of all edges incident to $e$ but not containing the color of $e$ such
that removing all edges colored by a color in $S$ leaves a graph with exactly
one even component.

######  Example 3.14.

The following edge coloring has a symmetric edge labeled $e$. Notice that
removing the edges colored blue and orange leave only a single connected
component with even order.

$e$

$e$

An edge coloring can also have symmetric edge incident to a leaf. Notice that
removing the edges colored orange as well as those colored blue in the
following graph coloring produces a graph with only a single connected
component with even order.

$e$

$e$

######  Theorem 3.15.

Let $(G,\kappa)$ be a proper edge coloring of a tree. If $G$ contains a
symmetric edge, then $\mathfrak{G}_{\kappa}\cong S_{V(G)}$.

###### Proof.

Let $e=\\{i,j\\}$ be a symmetric edge in $G$ with corresponding subset of
colors $S$. Let $H$ be the graph obtained by deleting all edges colored by a
color in $S$ and $m$ the least common multiple of the orders of odd-sized
connected components in $H$. Let

$\displaystyle\pi=\prod_{a\in[k]\setminus S}\tau_{a},$

with the product taken in any order. Then because the edge $e$ is the only
even-sized component in $\sigma$, Lemma 3.7 says that

$\displaystyle\pi^{m}=(i,j).$

Let $K_{i}$ and $K_{j}$ be the sets of colors of edges incident to $i$ and $j$
respectively. Let

$\displaystyle\sigma_{1}$ $\displaystyle=\prod_{a\in
K_{i}\setminus\\{\kappa(e)\\}}\tau_{a}$ $\displaystyle\sigma_{2}$
$\displaystyle=\prod_{a\in[k]\setminus K_{i}}\tau_{a}$

with products taken in any order. It’s clear that $\sigma_{2}(i)=i$, but
because $K_{i}\cap K_{j}=\\{\kappa(e)\\}$, we also have that
$\sigma_{1}(j)=j$. By Lemma 3.7, $\sigma=\sigma_{1}\tau_{\kappa(e)}\sigma_{2}$
is an $n$-cycle, and by the above observation,
$\sigma(i)=\sigma_{1}\tau_{\kappa(e)}(i)=\sigma_{1}(j)=j$. The transposition
$(i,j)$ and the $n$-cycle $\sigma$ with $\sigma(i)=\sigma(j)$ generate the
full symmetric group $S_{V(G)}$. ∎

The symmetric edge condition has allowed us to more efficiently search
colorings of trees by weeding out colorings which we know will give the
symmetric group. See Appendix B for some data on coloring groups on small
trees.

##  4 Applications

###  4.1 Generalized Toggle Groups

The following condition for a coloring group on a tree to be isomorphic to a
generalized toggle group is due to Jonathan Bloom.

######  Definition 4.1.

A word $w\in[k]^{\ell}$ is called a toggle word if every contiguous subword of
$w$ has at least two distinct letters that occur with odd parity.

######  Theorem 4.2.

Let $(G,\kappa)$ be a proper edge coloring of a tree. A necessary condition
for $\mathfrak{G}_{\kappa}$ to be a generalized toggle group is that for every
path, reading the edge colors along that path must be a toggle word.

###### Proof.

This follows from the following observation on toggle graphs. Let $G=P_{L}$
for some toggle group $T(L)$ and suppose that $w_{1}w_{2}\dots w_{\ell}$ is
the sequence elements of the base set corresponding to the coloring for a walk
in $G$ with no consecutive letters. Without loss of generality we can assume
no vertices of $G$ are repeated.

If each distinct label appears an even number of times, then each element
element is toggled in and out an equal number of times so this is a nontrivial
closed walk in the graph without consecutive repeated edges, so the walk must
be a cycle.

If exactly one label appears an odd number of times, call it $e$, then the
result of this walk is that $e$ is either toggled in or out of the initial
set, as all other labels are toggled in and out an even number of times. As no
vertices are repeated then we could also have taken the distinct path of
applying the toggle $\tau_{e}$, so $G$ must contain a cycle. This edge must
exist as $G$ arose from a toggle group.

As such if $G$ is acyclic and $\kappa$ corresponds to a coloring which arises
from a toggle group, then no nontrivial path of distinct vertices in $G$ can
have fewer than two colors which appear an odd number of times. ∎

######  Example 4.3.

The following edge coloring gives rise to a coloring group isomorphic to a
generalized toggle group. The family of subsets are the vertex labels.

$\\{2,3\\}$$\\{1,2,3\\}$$\\{1,2\\}$$\\{1\\}$$\emptyset$$\\{4\\}$$\\{3,4\\}$$\\{3,4,5\\}$$\\{3,5\\}$$\\{2,4\\}$$\\{2,4,5\\}$

The path from the vertex labeled $\\{2,3\\}$ to the vertex labeled $\\{3,5\\}$
corresponds to the toggle word

$w=13214354.$

Note that in Example 3.4, any path starting in the left-most block of vertices
(colored blue) and ending at the next vertex it encounters in that left-most
block must encounter every edge color in-between an even number of times. The
colors on this path will not be a toggle word, so the coloring group in this
example cannot be a generalized toggle group. A similar insight applies
generally to trees as stated in the next theorem.

######  Theorem 4.4.

Let $(G,\kappa)$ be a proper edge coloring of a tree $G$ with order $n\geq 3$.
If $\mathfrak{G}_{\kappa}$ is a generalized toggle group, then
$\mathfrak{G}_{\kappa}$ is primitive.

###### Proof.

Suppose $\mathfrak{G}_{\kappa}$ were not primitive. Then there would be at
least two blocks in a system of imprimitivity. Because $G$ is connected, there
must be some edge colored $a$ connecting two vertices $i$ and $j$ in the same
block. Furthermore, there must be an edge colored $b$ connecting $i$ to a
vertex $i^{\prime}$ in another block. By the definition of an imprimitive
coloring, there must then be an edge also colored $b$ connecting $j$ to some
$j^{\prime}$ in the same block as $i^{\prime}$. Then the path
$i^{\prime},i,j,j^{\prime}$ has word $aba$, which is not a toggle word,
contradicting the assumption that $\mathfrak{G}_{\kappa}$ is a generalized
toggle group. ∎

This result also follows from a more general result of Bloom and Saracino [1,
Theorem 4.2], specifically that an imprimitive toggle group $T(L)$ containing
a cycle on every element of $L$ will have that $L$ has the structure of a
product of sets, which must contain a cycle. Additionally Theorem 4.4 allows
us to apply Theorem 3.9(iii) to the particular case of a generalized toggle
group presented by an edge coloring of a path.

######  Theorem 4.5.

Let $(G,\kappa)$ be a proper edge coloring of a path. If
$\mathfrak{G}_{\kappa}$ is a generalized toggle group, then one of the
following statements holds:

  1. (i)

$n=\frac{q^{d}-1}{q-1}$ for $q$ a prime power, $d\geq 2$, and
$PGL(d,q)\subseteq\mathfrak{G}_{\kappa}\subseteq P\Gamma L(d,q)$.

  2. (ii)

$\mathfrak{G}_{\kappa}\cong M_{23}$, the Mathieu group.

  3. (iii)

$\mathfrak{G}_{\kappa}\cong S_{n}$.

###  4.2 Independence Posets

When Cameron and Fon-der-Flaass originally described the toggle group, they
were essentially considering it as a group structure on a distributive
lattice. While the generalized toggle group is an extension of these order
ideal toggles from a group-theoretic perspective to subsets of a finite set,
there has historically been considerably more focus on trying to understand
generalizations of this family of lattices from a combinatorial as well as
order-theoretic point of view. One particular family that serves as a
generalization are the trim lattices, first introduced by Hugh Thomas in [11].
Before we define these lattices, recall that an element $x$ of a lattice $L$
is _left modular_ if for any $y<z\in L$ the following equality holds
$y\vee(x\wedge z)=(y\vee x)\wedge z$.

######  Definition 4.6.

[11] A lattice is _trim_ if it has a maximal chain of $(n+1)$ left modular
elements as well as $n$ join-irreducible elements and $n$ meet irreducible
elements.

These lattices were further generalized by Thomas with Williams to a family of
posets known as independence posets, which contains many posets of
combinatorial and geometric interest. Importantly the set of independence
posets which are lattices is precisely the set of trim lattices. As such all
of the following are examples of independence posets, as explained in [12].

  * •

Distributive lattices

  * •

Tamari Lattices

  * •

Cambrian Lattices

  * •

Fuss-Cambrian Lattices

as well as many more. To be self-contained, we now follow the treatment of
[12] to define these objects, up to the omission of proofs.

For the remainder of the background on independence posets, let $G$ be a
directed acylic graph. A $G$-order is the partial order on $V(G)$ where
$g_{1}\geq g_{2}$ when there is a directed path from $g_{1}$ to $g_{2}$.
Recall that an independent set of $G$ is a subset where no two elements are
adjacent. To define an independence poset we first need the following
definitions.

######  Definition 4.7.

[12, Definition 1.2] A pair ($D$, $U$) of independent sets of $G$ is called
_orthogonal_ if there is no edge in $G$ from an element of $D$ to an element
of $U$. An orthogonal pair of independent sets ($D$, $U$) is called _tight_ if
whenever any element of $D$ is increased (removed and replaced by a larger
element with respect to the $G$-order), any element of $U$ is decreased, or a
new element is added to either $D$ or $U$, then the result is no longer an
orthogonal pair of independent sets. We abbreviate tight orthogonal pair by
top, and we write $\textbf{top}(G)$ for the set of all tops of $G$.

It turns out that when $G$ is directed and acyclic then specifying either of
$U$ or $D$ gives a bijection to the independent sets of $G$. This result is
more formally stated as follows.

######  Theorem 4.8.

[12, Theorem 1.2] Let $I$ be an independent set of a directed acyclic graph
$G$. Then there exists a unique $(I,U)\in\textbf{top}(G)$ and a unique
$(D,I)\in\textbf{top}(G)$.

To state the last required definition, let $\ell$ be a fixed linear extension
of the $G$-order and let $\ell^{\prime}$ be a fixed dual linear extension of
the $G$-order.

######  Definition 4.9.

[12, Definition 1.3] The flip of $(D,U)\in\textbf{top}(G)$ at an element $g\in
G$ is the tight orthogonal pair $flip_{g}(D,U)$ defined as follows: if
$g\notin D$ and $g\notin U$, the flip does nothing. Otherwise, preserve all
elements of $D$ that are not less than $g$ and all elements of $U$ that are
not greater than $g$ (and delete all other elements); after switching the set
to which $g$ belongs, then greedily complete $D$ and $U$ to a tight orthogonal
pair in the orders $\ell^{\prime}$ and $\ell$, respectively.

These flips are all well defined, and in fact involutions, as shown in [12,
Lemma 3.2]. One additional consequence of [12, Lemma 3.2] that we mention now
is that if $g,h$ are incomparable elements of a $G$-order, then the associated
flips commute. All together an independence poset is defined as follows.

######  Definition 4.10.

[12, Definition 1.4] The _independence poset_ on $\textbf{top}(G)$ is the
reflexive and transitive closure of the relations
$(D,U)\lessdot(D^{\prime},U^{\prime})$ if there is some $g\in U$ such that
$flip_{g}(D,U)=(D^{\prime},U^{\prime}).$

For full details that this is in fact well defined as a poset, see [12, Lemma
3.3]. The flips then naturally label the edges in the Hasse diagram of
$\textbf{top}(G)$ by elements of $G$. Importantly for us, this is clearly a
proper edge labeling of the Hasse diagram, so one can then ask about the
coloring group generated by these labels. We can fully describe these groups
with the following result.

######  Example 4.11.

The independence poset on the increasing orientation of $P_{3}$

123$(\emptyset,13)$$(3,2)$$(2,1)$$(1,3)$$(13,\emptyset)$13321

######  Theorem 4.12.

Let $P=\textbf{top}(G)$ be an independence poset with $|P|=n$.

  * •

If $G$ is connected, then the coloring group generated by the labeling of the
Hasse diagram of $P$ contains $A_{n}$.

  * •

If $G$ is not connected, then the coloring group is isomorphic to the direct
product of the coloring groups restricted to the connected components.

The first statement requires nontrivial machinery which we now explain.

To prove this, we first recall the following definitions due to Striker [9].
The first is that a toggle group is said to be _toggle-alternating_ if it
contains the alternating group. The second and more involved sequence of
definitions are those needed for a collection to be _inductively toggle-
alternating_.

######  Definition 4.13.

[9, Definition 2.20] Given $e\in E$ and $L\subseteq 2^{E}$, define
$L_{e}:=\\{X\in L\ |\ e\in X\\}$ to consist of all the subsets in $L$ that
contain $e$ and $L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}}:=\\{X\in L\ |\
e\notin X\\}$ to be all the subsets in $L$ that do not contain $e$. For any
subset $S\subseteq L$, let $\tau_{e}(S)=\left\\{\tau_{e}(X)\mid X\in
S\right\\}$.

######  Definition 4.14.

[9, Definition 2.5] Given $L\subseteq 2^{E}$, let an _essentialization_ of
$(L,E)$ be $(L^{\prime},E^{\prime})$ where $E^{\prime}$ and $L^{\prime}$ are
as follows. Every $e\in E^{\prime}$ must be an element $e\in E$ such that
there exist $X,Y\in L$ with $e\in X$ and $e\not\in Y$. That is, no element of
$E^{\prime}$ may be contained in all or none of the subsets in $L$. Also,
consider subsets $Z\subseteq E$ with $|Z|>1$ such that if $e\in Z$ and $e\in
W\in L$, then $Z\subseteq W$. For any maximal such $Z$, we exclude all
elements of $Z$ except one from $E^{\prime}$. Let $L^{\prime}=\\{X\cap
E^{\prime}\ |\ X\in L\\}$.

######  Definition 4.15.

[9, Definition 2.21] We define the collection of _inductively toggle-
alternating_ sets $L$ to be the smallest collection of $L\subseteq 2^{E}$,
with essentializations $(L^{\prime},E^{\prime})$, such that:

  1. 1.

If $|E^{\prime}|\leq 4$, then $T(L)$ is toggle-alternating.

  2. 2.

If $|E^{\prime}|\geq 5$, then there exists $e\in E^{\prime}$ such that at
least one of the following holds:

    1. (a)

$L_{e}$ is inductively toggle-alternating, $L_{e}\cup\tau_{e}(L_{e})=L$, and
$L_{e}\cap\tau_{e}(L_{e})\neq\emptyset$, or

    2. (b)

$L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}}$ is inductively toggle-
alternating,
$L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}}\cup\tau_{e}(L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}})=L$,
and
$L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}}\cap\tau_{e}(L_{\accentset{\rule{2.79996pt}{0.8pt}}{e}})\neq\emptyset$.

This definition allows for the statement of the following result, which we
will generalize.

######  Theorem 4.16.

[9, Theorem 2.22] If $L$ is inductively toggle-alternating, then it is toggle-
alternating.

Roughly, we will generalize the above definitions and the hypothesis of
Theorem 4.16 from the setting of toggle groups to that of coloring groups. In
the style of [9], we now refer to a coloring group $\mathfrak{G}_{\kappa}$, or
equivalently the pair $(G,\kappa)$, as being _color-alternating_ if
$\mathfrak{G}_{\kappa}$ contains the alternating group on the vertex set of
$G$. This then allows us to describe a straightforward generalization of
inductively toggle-alternating.

######  Definition 4.17.

Let $F$ be a collection of connected graphs with proper surjective edge
colorings such that the following hold.

  1. 1.

If $(G,\kappa)\in F$ with $|\kappa(E(G))|\leq 4$ the group
$\mathfrak{G}_{\kappa}$ is color-alternating.

  2. 2.

If $(G,\kappa)\in F$ with $|\kappa(E(G))|\geq 5$ there is some color $i$ such
that the vertices of $G$ can be partitioned into two disjoint subsets
$G_{1},G_{2}$ (thought of as induced subgraphs) such that

    1. (a)

$\tau_{i}(G_{1})\cap G_{1}\neq\emptyset$,

    2. (b)

$\tau_{i}(G_{1})\cup G_{1}=G$, $(G_{1},\kappa|_{G_{1}})\in F$,

    3. (c)

the only edges that connect $G_{1}$ and $G_{2}$ are colored $i$.

We call the elements of $F$ inductively color-alternating.

######  Theorem 4.18.

If $(G,\kappa)$ is inductively color-alternating, then $\mathfrak{G}_{\kappa}$
is color-alternating.

###### Proof.

The proof is almost exactly the proof of 4.16 due to Striker in [9], which is
essentially the proof in the case of order ideals due to Cameron and Fon-der-
Flaass in [2].

For the remainder of the proof, $C$ will denote the codomain of $\kappa$ (with
$C^{\prime}$ the associated codomain of $\kappa^{\prime}$). After relabeling
we will identify $C$ with $\\{1,\dots,|C|\\}$.

Note for $|C|\leq 4$, we have required in the definition of inductively color-
alternating that $\mathfrak{G}_{\kappa}$ be color-alternating (this is because
in the proof below we need $A_{|V(G)|}$ to be simple, and the alternating
group ${A}_{n}$ is simple for $n\geq 5$ but not for $n=4$), so the case that
$|C|\leq 4$ serves as one of our base cases. The other, which we call the
exceptional base case, is when $|V(G)|=4$ and $|C|>4$. In this exceptional
base case, $G$ is either $K_{4}$ or $K_{4}$ with an edge removed. If $G=K_{4}$
minus an edge, and $|C|=5$ then $\mathfrak{G}_{\kappa}$ is the symmetric group
as every edge has a distinct color. If $G=K_{4}$ and $|C|=6$, then
$\mathfrak{G}_{\kappa}$ is the symmetric group for the same reason. If
$G=K_{4}$ and $|C|=5$, then without loss of generality we can assume the edges
$(1,2)$ and $(3,4)$ have the same color, as exactly one color is repeated. If
we just ignore these two edges, the remaining edges form a connected graph on
four vertices with all distinct edge colors, so the corresponding group is the
symmetric group. We have shown that our base cases are all color-alternating.

Now suppose $|C|\geq 5$. Also, suppose for all
$(G^{\prime},\kappa^{\prime})\in F$ with $|C^{\prime}|<|C|$ we have
$(G^{\prime},\kappa^{\prime})$ is color-alternating. Let $i\in C$ be the color
required by condition $(2)$ of Definition 4.17, since $(G,\kappa)$ is
inductively color-alternating. Following from the definition of inductively
color-alternating, $G=G_{1}\cup G_{2}$, $|G_{1}|>|G_{2}|>0$ as
$G_{1}\cup\tau_{i}(G_{1})=G$ and $G_{1}\cap\tau_{i}(G_{1})\neq\emptyset$ so
$G_{2}$ is a proper subset of $\tau(G_{1})$, the coloring pair obtained by
considering $G_{1}$ as an induced subgraph of $G$ with the inherited proper
edge coloring $(G_{1},\kappa|_{G_{1}})=(G_{1},\kappa^{\prime})$ is inductively
color-alternating, and $i\notin\kappa^{\prime}(E(G_{1}))$. Importantly
$\tau_{i}$ acts trivially on $G_{1}$ when the vertex set is restricted.
Additionally we are here using the hypothesis that the only edges that connect
$G_{1}$ and $G_{2}$ are colored $i$, so that the restricted action of the
coloring of $\kappa^{\prime}$ is the same as that of $\kappa$. By induction,
$\mathfrak{G}_{\kappa^{\prime}}$ contains the alternating group on $|G_{1}|$
elements. We first assume that $|G_{1}|\geq 5$, so $A_{|G_{1}|}$ is simple.
Since $A_{G_{1}}$ is simple and $|G_{1}|>|G_{2}|$, the subgroup $K$ of
$\mathfrak{G}_{\kappa}$ fixing $G_{2}$ pointwise induces at least $A_{G_{1}}$
on $G_{1}$. If instead $|G_{1}|\leq 4$ then $|C^{\prime}|\leq 4$, and we
satisfy condition $(1)$ of Definition 4.17 or we are in an exceptional base
case as no simple graph $G^{\prime}$ on with $|G^{\prime}|=4$ can have more
than 6 edges and the cases where $|G^{\prime}|=4$ and $|C|>4$ are the
exceptional base cases. In either event the subgroup $K$ of
$\mathfrak{G}_{\kappa}$ fixing $G_{2}$ pointwise induces at least $A_{G_{1}}$
on $G_{1}$.

Then in either case, $G_{1}\cup\tau_{i}(G_{1})=G$ and $\tau_{i}(G_{1})\cap
G_{1}\neq\emptyset$, so $K$ and the conjugate subgroup
$K^{\tau_{i}}:=\left\\{\tau_{i}k\tau_{i}\ |\ k\in K\right\\}$ generate an
alternating or symmetric group on $G$. ∎

Before proving Theorem 4.12, we mention a few more necessary results on the
structure of independence posets from [12]. The first is the _tight orthogonal
pair recursion_. For any $g\in G$, $\\{g\\}$ is an independent set, there are
unique $D,U$ such that $(D,\\{g\\})=m_{g}$ and $(\\{g\\},U)=j_{g}$ are tight
orthogonal pairs. Let $\textbf{top}_{g}(G)=[\hat{0},m_{g}]$ and
$\textbf{top}^{g}(G)=[j_{g},\hat{1}]$. In the case where $g$ is an extremal
(minimal or maximal) element of the $G$-order, these two intervals in fact
partition the independence poset. Formally this is stated as follows.

######  Lemma 4.19.

[12, Lemma 3.7] Let $G$ be an acyclic directed graph. If $g$ is an extremal
element of $G$ then
$\textbf{top}(G)=\textbf{top}_{g}(G)\cup\textbf{top}^{g}(G)$. Furthermore,

  * •

If $g$ is minimal, $(D,U)\in\textbf{top}_{g}(G)$ if and only if $g\in U$.

  * •

If $g$ is maximal, $(D,U)\in\textbf{top}^{g}(G)$ if and only if $g\in D$.

In particular, if $x\in\textbf{top}^{g}(G)$ and $y\in\textbf{top}_{g}(G)$ then
$x\not\leq y$.

While we do not repeat the proof of Lemma 4.19 we do note that one essential
feature of the argument shows that when $g$ is an extremal element, for any
$g^{\prime}\neq g$, both
$flip_{g^{\prime}}(\textbf{top}_{g}(G))=\textbf{top}_{g}(G)$ and
$flip_{g^{\prime}}(\textbf{top}^{g}(G))=\textbf{top}^{g}(G)$. In particular
this provides potential candidates for $i$, $G_{1}$, and $G_{2}$ to apply
Theorem 4.18. What then remains is to understand the action of $flip_{g}$ when
$g$ is extremal. To that end we use the following results of [12].

######  Lemma 4.20.

[12, Lemma 3.9] Let $G$ be a directed acyclic graph.

  * •

If $g$ is minimal and $(D,U)\in\textbf{top}_{g}(G)$, then
$flip_{g}(D,U)=(D\cup\\{g\\},U^{\prime})$ for some $U^{\prime}$.

  * •

If $g$ is maximal and $(D,U)\in\textbf{top}^{g}(G)$, then
$flip_{g}(D,U)=(D^{\prime},U\cup\\{g\\})$ for some $D^{\prime}$.

Before stating the last result, we mention the following notation. If $G$ is a
directed acyclic graph and $g\in G$, $G_{g}$ is $G\setminus\\{g\\}$ and
$G_{g}^{\circ}$ is $G\setminus(\\{g\\}\cup\\{g^{\prime}|(g,g^{\prime})\text{
or }(g^{\prime},g)\in E(G)\\})$.

######  Theorem 4.21.

[12, Theorem 3.10] Let $g$ be an extremal element of an acyclic directed graph
$G$. Then

$\displaystyle(D,U)$ $\displaystyle\mapsto(D,U\setminus\\{g\\}\\}\text{ is a
bijection
}\begin{cases}\textbf{top}_{g}(G)\simeq\textbf{top}(G_{g}^{\circ})&\text{if
}g\text{ minimal}\\\ \textbf{top}_{g}(G)\simeq\textbf{top}(G_{g})&\text{if
}g\text{ maximal}\end{cases}$ $\displaystyle(D,U)$
$\displaystyle\mapsto(D\setminus\\{g\\},U\\})\text{ is a bijection
}\begin{cases}\textbf{top}^{g}(G)\simeq\textbf{top}(G_{g})&\text{if }g\text{
minimal}\\\ \textbf{top}^{g}(G)\simeq\textbf{top}(G_{g}^{\circ})&\text{if
}g\text{ maximal}\end{cases}$

This recursive structure description is the final tool we need.

###### Proof of Theorem 4.12.

We note that the element $\tau_{i}$ induced by the proper edge coloring of the
Hasse diagram of $\textbf{top}(G)$ coming from the flips is exactly $flip_{i}$
so we will continue to use $flip_{i}$. To show the first statement, notice
that if $G$ is connected, so is the Hasse diagram of the $G$-order.
Particularly, the Hasse diagram of the $G$-order is the subgraph of $G$
obtained by deleting all edges $u,v$ if there is a longer path from $u$ to
$v$.

Recall that for a finite connected poset $P$, there is always some extremal
element $g$ for which the poset obtained by removing $g$ is connected.
Importantly if $P$ is a $G$-order then the poset $P^{\prime}$ obtained by the
deletion of this extremal element $g$ is a $G_{g}$-order, so $G_{g}$ is still
connected as a graph.

Now to show that the coloring groups of independence posets with connected
directed acyclic graphs are inductively color-alternating, we show the
inductive step, so we assume $|G|>4$. The base cases where $|G|\leq 4$ were
checked by computer and the code is included in the repository linked in
Appendix B.

First choose an extremal element $g$ such that the Hasse diagram of the
$G$-order is connected. We can assume $g$ is maximal, as otherwise we can swap
the role of $\textbf{top}_{g}(G)$ and $\textbf{top}^{g}(G)$, so we have
$G_{1}=\textbf{top}_{g}(G)$ and $G_{2}=\textbf{top}^{g}(G)$. Note that
$|G_{1}|>|G_{2}|$ as $G_{1}$ is in bijection with independent sets of $G$ that
do not contain $g$, whereas $G_{2}$ is in bijection with independent sets of
$G$ that do not contain $g$ or a neighbor of $g$.

By Lemma 4.19 we know that $G_{1}$ and $G_{2}$ partition the Hasse diagram of
$\textbf{top}(G)$. Additionally by Lemma 4.20 and Lemma 4.19 we have that
$flip_{g}(G_{2})\subseteq G_{1}$, so $G_{1}\cap flip_{g}(G_{1})\neq\emptyset$
as $|G_{1}|>|G_{2}|$. Furthermore by the discussion preceding Lemma 4.20 we
know that the only edges connecting $G_{1}$ and $G_{2}$ are colored by $g$.
Finally note that by the choice of $g$ and Theorem 4.21,
$G_{1}=\textbf{top}_{g}(G)\simeq\textbf{top}(G_{g})$ which is an independence
poset of a connected directed acyclic graph with $|G_{g}|<|G|$. As such the
family of independence posets from connected directed acyclic graphs with
coloring given by the labels of the flips is inductively color-alternating,
and thus color alternating.

To prove the second part, note that no two elements of a connected component
of $G$ are comparable in the $G$-order, so their associated flips commute. As
such the coloring group is immediately seen to be isomorphic to the direct
product of the groups of the connected components. ∎

##  Appendix A Constructions of Coloring Groups on Trees

In this appendix, we present some particular constructions of
$S_{n},A_{n},D_{n},$ and (when $n$ is even,) $B_{n/2}$ as coloring groups on
trees of size $n$.

######  Example A.1.

For a connected graph of order $n$, let $(G,\kappa)$ be the edge coloring that
gives each edge a distinct color. Then it’s clear that
$\mathfrak{G}_{\kappa}=S_{n}$.

On the other extreme, it’s possible to construct $S_{n}$ with very few colors.

######  Example A.2.

Given any proper edge coloring $(T,\kappa)$ of a tree $T$ of order $n$, let
$\kappa^{\prime}$ be the coloring obtained by changing the color of an edge
incident to a leaf to a new unique color. The symmetric edge condition in
Theorem 3.15 guarantees that $\mathfrak{G}_{\kappa^{\prime}}=S_{n}$. In this
way we can realize the symmetric group $S_{n}$ on any tree of order $n$ with
just $\Delta(T)+1$ colors, where $\Delta(T)$ is the maximum degree of $T$. In
particular, we can realize any symmetric group on a path with three colors.
For example, the coloring

has corresponding coloring group $S_{10}$.

In order to realize $A_{n}$ as a coloring group, all colors must appear on an
even number of edges. In particular, this means that the order $n$ of our tree
must be odd. It turns out that we can realize $A_{n}$ as a coloring group on a
tree whenever $n>5$ and $n$ is odd.

######  Example A.3.

Color the path graph $P_{2k+1}$ by $1,2,\dots,k,1,2,\dots,k$. Then
$(\tau_{1}\tau_{k})^{2}$ is a three-cycle. Label the vertices so that
$(\tau_{1}\tau_{k})^{2}=(1,2,3)$. Then any product $\sigma$ of all the
generators which ends in $\tau_{k}\tau_{1}\tau_{2}$ sends $1\to 2\to 3$. Label
the remaining vertices so that $\sigma(i)=i+1$. The long cycle $\sigma$ and
the three-cycle $(\tau_{1}\tau_{k})^{2}$ generate all of $A_{n}$. For example,

has corresponding coloring group $A_{9}$.

Note that this construction fails for $n=5$ because, as we’ll see in the
following example, the coloring we obtain must be $D_{5}$.

We can construct $D_{n}$ on the path graph with the minimal proper edge
coloring.

######  Example A.4.

The proper edge coloring of $P_{n}$ with two colors yields the dihedral group
$D_{n}$. A nice way to see this is to consider the vertices of a regular
$n$-gon and connect them into a path in a zig-zag fashion like so:

From this illustration, we can clearly see that the two generators correspond
to two reflections that generate $D_{n}$.

By the proof of theorem 3.11, we can construct the group $B_{m}$ of signed
permutations on a tree of order $n=2m$ by joining two identical trees whose
corresponding coloring group is the symmetric group $S_{m}$ with an edge of a
unique color.

######  Example A.5.

Let $(T,\kappa)$ be the proper edge coloring of the star graph on $n$
vertices. Connect two copies of $T$ at their centers by a new edge colored
$n+1$. The resulting color group is $B_{n}$. For example, the coloring group
of

is $B_{4}$.

##  Appendix B Coloring Groups on Small Trees

The following table lists the coloring groups presented by proper edge
colorings of trees up to 12 vertices computed using Sage222Code available at
https://github.com/wilsoa/Coloring-Groups [8]. Groups isomorphic to
$S_{n},A_{n},D_{n}$ or $B_{m}$ are omitted as their constructions are detailed
above. The description in each row comes from GAP’s [4] structure_description
method. A sample coloring realizing the group is given in the table either as
a sequence of edge colors on a path or as a reference to another example if it
is not possible to realize that group on a path.

Degree | Description | Order | Primitive? | Coloring
---|---|---|---|---
7 | $GL(3,2)$ | 168 | Yes | Example 2.1
9 | $(C_{3}\times C_{3}\times C_{3})\rtimes S4$ | 648 | No | Example B.1
10 | $(C_{5}\times C_{5})\rtimes D_{4}$ | 200 | No | 1,2,1,3,1,2,1,3,1
| $C_{2}\times S_{5}$ | 240 | No | 1,2,1,3,1,3,1,2,1
| $(A_{5}\times A_{5})\rtimes(C_{2}\times C_{2})$ | 14400 | No | 1,2,1,2,1,3,1,3,1
12 | $(C_{3}\times C_{3})\rtimes((C_{2})^{4}\rtimes C_{2})$ | 288 | No | 1,2,1,3,1,2,1,3,1,2,1
| $(C_{2}\times C_{2})\rtimes((C_{2})^{4}\rtimes D_{6})$ | 768 | No | 1,2,3,2,1,2,1,2,3,2,1
| $(C_{3}\times C_{3}\times C_{3})\rtimes(C_{2}\times S_{4})$ | 1296 | No | 1,2,3,2,3,2,1,2,1,2,3
| $(C_{4}\times C_{4}\times C_{4})\rtimes S_{4}$ | 1536 | No | Example 3.12
| $(C_{2})^{2}\rtimes((C_{2})^{4}\rtimes((S_{3})^{2}\rtimes C_{2}))$ | 4608 | No | 1,2,1,3,1,3,1,3,1,2,1
| $(C_{3})^{4}\rtimes((C_{4}\times C_{2})\rtimes D_{4})$ | 5184 | No | Example B.2
| $({C_{2}})^{6}\rtimes(((C_{3})^{2}\rtimes C_{3})\rtimes(C_{2})^{2})$ | 6912 | No | Example 3.5
| $(C_{3})^{4}\rtimes((C_{2})^{3}\rtimes S_{4})$ | 15552 | No | 1,2,3,4,3,2,1,4,1,2,3
| $((C_{2})^{5}\rtimes A_{6})\rtimes C_{2}$ | 23040 | No | Example B.3
| $(C_{3})^{4}\rtimes((C_{2})^{4}\rtimes S_{4})$ | 31104 | No | Example B.4
| $(C_{2})^{6}\rtimes((C_{3})^{3}\rtimes(C_{2}\times S_{4}))$ | 82944 | No | Example B.5
| $(A_{6}\times A_{6})\rtimes D_{4}$ | 1036800 | No | 1,2,1,2,1,3,1,3,1,3,1

Finally, we collect example colorings for groups in the above table which have
not yet appeared.

######  Example B.1.

Coloring realizing the group of degree 9 and order 648:

######  Example B.2.

Coloring realizing the group of degree 12 and order 5184:

######  Example B.3.

Coloring realizing the group of degree 12 and order 23040:

######  Example B.4.

Coloring realizing the group of degree 12 and order 31104:

######  Example B.5.

Coloring realizing the group of degree 12 and order 82944:

## References

  * [1] Jonathan S. Bloom and Dan Saracino  “Transitive generalized toggle groups containing a cycle”, 2023  arXiv:2310.11387 [math.CO]
  * [2] P.. Cameron and D.. Fon-Der-Flaass  “Orbits of antichains revisited”  In _European J. Combin._ 16.6, 1995, pp. 545–554  DOI: 10.1016/0195-6698(95)90036-5
  * [3] David Einstein and James Propp  “Combinatorial, piecewise-linear, and birational homomesy for products of two chains”  In _Algebraic Combinatorics_ 4.2 MathOA foundation, 2021, pp. 201–224  DOI: 10.5802/alco.139
  * [4] “GAP – Groups, Algorithms, and Programming, Version 4.12.2”, 2022  The GAP Group  URL: https://www.gap-system.org
  * [5] Darij Grinberg and Tom Roby  “Iterative properties of birational rowmotion I: generalities and skeletal posets”  In _Electron. J. Combin._ 23.1, 2016, pp. Paper 1.3340  DOI: 10.37236/4334
  * [6] Darij Grinberg and Tom Roby  “Iterative properties of birational rowmotion II: rectangles and triangles”  In _Electron. J. Combin._ 22.3, 2015, pp. Paper 3.4049  DOI: 10.37236/4335
  * [7] Gareth A. Jones  “Primitive permutation groups containing a cycle”  In _Bull. Aust. Math. Soc._ 89.1, 2014, pp. 159–165  DOI: 10.1017/S000497271300049X
  * [8] The Sage Developers  “SageMath, the Sage Mathematics Software System (Version 9.1.0)”, 2020  URL: https://www.sagemath.org
  * [9] Jessica Striker  “Rowmotion and generalized toggle groups”  In _Discrete Math. Theor. Comput. Sci._ 20.1, 2018, pp. Paper No. 1726
  * [10] Jessica Striker and Nathan Williams  “Promotion and rowmotion”  In _European J. Combin._ 33.8, 2012, pp. 1919–1942  DOI: 10.1016/j.ejc.2012.05.003
  * [11] Hugh Thomas  “An analogue of distributivity for ungraded lattices”  In _Order_ 23.2-3, 2006, pp. 249–269  DOI: 10.1007/s11083-006-9046-9
  * [12] Hugh Thomas and Nathan Williams  “Independence posets”  In _J. Comb._ 10.3, 2019, pp. 545–578  DOI: 10.4310/JOC.2019.v10.n3.a5


# On skew corner-free sets

Cosmin Pohoata  and  Dmitrii Zakharov

###### Abstract.

We construct skew corner-free sets in $[n]^{2}$ of size $n^{5/4}$, thereby
disproving a conjecture of Kevin Pratt. We also show that any skew corner-free
set in $\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$ must have size at most
$q^{(2-c)n}$, for some positive constant $c$ which depends on $q$.

Department of Mathematics, Emory University, Atlanta, GA. Email:
<EMAIL_ADDRESS>Research supported by NSF Award DMS-2246659.

Department of Mathematics, Massachusetts Institute of Technology, Cambridge,
MA. Email<EMAIL_ADDRESS>Research supported by the Jane Street Graduate
Fellowship.

##  1\. Introduction

Motivated by matrix multiplication algorithms, Pratt [8] asked the following
nice question: what is the largest subset of $[n]^{2}$ which does not contain
‘skew corners’, i.e. triples of points of the form

(1) $(x,y),(x,y+d),(x+d,y^{\prime})$

for $d\neq 0$ and $x,y,y^{\prime}$ arbitrary?

We call such sets skew corner-free sets. Putting $y=y^{\prime}$ in the above,
we get that such a set does not contain regular corners
$(x,y),(x+d,y),(x,y+d)$. Determining the maximum size of a subset of $[n]^{2}$
without regular corners is a well-studied problem in additive combinatorics.
See for example [4] and the references therein for some background. Given this
connection to regular corner-free sets, Shkredov’s result from [9] immediately
implies that a skew corner-free set $S\subset[n]^{2}$ satisfies
$|S|=O\left(n^{2}/(\log\log n)^{c}\right)$, for some absolute constant $c>0$.
On the other hand, Petrov [6] constructed a skew corner free set in $[n]^{2}$
of size $\Omega(n\log n/\sqrt{\log\log n})$, and Pratt [8] conjectured that
any such set in $[n]^{2}$ has size $O(n^{1+\varepsilon})$ for any
$\varepsilon>0$. Furthermore, Pratt showed that such a result would show that
certain approaches to matrix multiplication cannot achieve a running time of
$O(n^{2+\varepsilon})$. We provide a construction which disproves this
prediction.

######  Theorem 1.1.

There exists a skew corner-free set $S\subset[n]^{2}$ of size
$\Omega(n^{5/4})$.

The main idea is to take advantage of a well-known property of the (affine
version) of the classical Hermitian unital over $\mathbb{F}_{p^{2}}^{2}$,
object which was also used by Mattheus–Verstraete [5] in the recent
breakthrough lower bound construction for the Ramsey number $R(4,t)$. We
discuss the proof of Theorem 1.1 in Section 2.

While Theorem 1.1 shows skew corner-free sets in $[n]^{2}$ may not always have
size $O(n^{1+\varepsilon})$ for any $\varepsilon>0$, we believe that such sets
should in the very least still have size $O(n^{2-c})$ for some absolute
constant $c>0$. Establishing this fact already seems like an interesting
problem, as there exist standard examples of corner-free sets in $[n]^{2}$ of
size $n^{2-o(1)}$. However, it does not seem that the usual Fourier analytic
methods can take advantage of the stronger condition of the set being skew
corner free in any significant manner. In Section 3, we show a result in this
spirit for the finite field model of this problem.

######  Theorem 1.2.

Let $q\geqslant 2$ be a prime and let
$S\subset\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$ be any set without
triples of the form $(\ref{skew})$ with $x,y,y^{\prime}\in\mathbb{F}_{q}^{n}$
and $d\in\mathbb{F}_{q}^{n}\setminus{0}$. Then,

$|S|\leqslant 3q^{(2-c_{q})n},$

where the exponent $c_{q}$ is a positive constant depending on $q$ defined as

$q^{1-c_{q}}=\inf_{0<x<1}x^{-(q-1)/3}(1+x+\ldots+x^{q-1}).$

Here we think of $q$ as fixed and as $n$ going to infinity. As the definition
of $c_{q}$ might already suggest to the experienced reader, the proof of
Theorem 1.2 will use the so-called Croot-Lev-Pach lemma, famously introduced
in [2], together with some of the ideas of Ellenberg and Gijswijt from their
resolution of the cap set problem [3]. Qualitatively speaking, it is perhaps
important to highlight that Theorem 1.2 serves as a certificate that the skew
corner-free problem in $\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$ does not
obey the induced matching barrier described in [1], where Christandl, Fawzi,
Ta, and Zuiddam show that the recent polynomial method as long as related
tensor methods for upper bounding the Shannon capacity (including slice rank,
subrank, analytic rank, geometric rank, and G-stable rank) cannot yield a
similar bound for the regular corner-free sets in
$\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}$.

##  2\. Proof of Theorem 1.1

Let $p\sim n^{1/4}$ be a prime and let $q=p^{2}$. For $a\in\mathbb{F}_{q}$ let
$\bar{a}=a^{p}$ be the Galois conjugate and let $N(a)=a\bar{a}=a^{p+1}$ be the
norm. Consider the affine version of the Hermitian unital in
$\mathbb{F}_{q}^{2}$:

$Q=\\{(a,b)\in\mathbb{F}_{q}^{2}:~{}N(a)+N(b)=1\\}.$

It is well-known that $|Q|\sim q^{3/2}$ and for each point $x\in Q$ there
exists a ‘tangent’ $\mathbb{F}_{q}$-line $\ell_{x}\subset\mathbb{F}_{q}^{2}$
such that $\ell_{x}\cap Q=\\{x\\}$. In other words, $Q$ forms a so-called
Nikodym set in $\mathbb{F}_{q}^{2}$. Indeed, if $x=(a,b)$ lies on $Q$ then we
can define

$\ell_{x}=\\{(a+t\bar{b},b-t\bar{a}),~{}t\in\mathbb{F}_{q}\\},$

where $\bar{a}=a^{p}$ denotes the Galois conjugate. Then we can write

$N(a+t\bar{b})+N(b-t\bar{a})=(a+t\bar{b})(\bar{a}+\bar{t}b)+(b-t\bar{a})(\bar{b}-\bar{t}a)=(1+N(t))(N(a)+N(b))=1+N(t)$

and so the point $(a+t\bar{b},b-t\bar{a})$ belongs to $Q$ if and only if
$N(t)=0$. But $N(t)=t^{p+1}=0$ implies $t=0$ finishing the proof of the claim.

Now we put

$S^{\prime}=\\{(x,y)\in\mathbb{F}_{q}^{2}\times\mathbb{F}_{q}^{2}:~{}x\in
Q,~{}y\in\ell_{x}\\}.$

Note that $|S^{\prime}|=|Q|q\sim q^{5/2}$. Suppose that $S^{\prime}$ contains
a triple of the form $(\ref{skew})$, i.e. we have points $x,x+d\in Q$,
$y,y+d\in\ell_{x}$ and $y^{\prime}\in\ell_{x+d}$ for some $d\neq 0$. Then note
that $x+d=x+(y+d)-y$, i.e. $x+d$ is an affine combination of points lying on
$\ell_{x}$ and so $x+d$ itself has to lie on $\ell_{x}$. But then this
contradicts the property that $Q\cap\ell_{x}=\\{x\\}$. So $S^{\prime}$ is a
skew corner-free set in $\mathbb{F}_{q}^{2}\times\mathbb{F}_{q}^{2}$.

Now let us view $\mathbb{F}_{q}^{2}$ as $\mathbb{F}_{p}^{4}$ and let
$B=[p/10]^{4}\subset\mathbb{F}_{p}^{4}$ be a standard box. For a random shift
$s$, we have $|(S^{\prime}-s)\cap(B\times B)|\gtrsim q^{5/2}$. Let
$\psi:B\rightarrow[n]$ be the map $\psi:(b_{0},b_{1},b_{2},b_{3})=\sum
p^{i}b_{i}$ and define

$S=\psi((S^{\prime}-s)\cap(B\times B))\subset[n]^{2}.$

It is clear that $|S|\sim q^{5/2}\sim n^{5/4}$ and that $\psi$ preserves the
property of being skew corner-free. So $S$ is skew corner-free.

##  3\. Proof of Theorem 1.2

Let $X=\pi(S)\subset\mathbb{F}_{q}^{n}$ denote the projection of $S$ onto the
first coordinate. For each $x\in X$, let $C_{x}\subset\mathbb{F}_{q}^{n}$
denote the set of elements $y\in\mathbb{F}_{q}^{n}$ with the property that
$(x,y)$ is a point in $S$. Morally, the elements of $C_{x}$ identify the
points of $S$ in the ‘column’ above $x$, so we will sometimes refer to the set
$C_{x}$ as the column above $x$. Clearly, $|S|=\sum_{x\in X}|C_{x}|$. In order
to bound this sum we are going to use the so-called Croot-Lev-Pach lemma, in
the same style as Ellenberg and Gijswijt used it in [3]. We first briefly
recall the statement and introduce some useful notation for later.

Let $\mathcal{V}(q,n)$ be the $\mathbb{F}_{q}$-vector space of functions $f:\
\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$. A basis for this vector space is given
by the set of monomials

$M(q,n)=\left\\{x_{1}^{a_{1}}\ldots x_{n}^{a_{n}}:\ 0\leqslant a_{i}\leqslant
q-1\right\\}.$

Given a positive integer $d$, let $M_{d}(q,n)$ be the set of monomials in
$M(q,n)$ of degree at most $d$, and let
$\mathcal{V}_{d}(q,n)\subset\mathcal{V}(q,n)$ be the set of polynomials of
degree at most $d$ over $\mathbb{F}_{q}$ spanned by these monomials. Finally,
let $m_{d}(q,n)=|M_{d}(q,n)|$. Using this terminology, the general form of the
Croot-Lev-Pach lemma over $\mathbb{F}_{q}^{n}$ can be stated as follows.

######  Lemma 3.1.

Let $f\in\mathcal{V}_{d}(q,n)$ and let $A$ denote the $q^{n}\times q^{n}$
matrix with entries $A_{y,z}=f(y,z)$ for $y,z\in\mathbb{F}_{q}^{n}$. Then,
$\operatorname{rank}(A)\leqslant 2\cdot m_{d/2}(q,n)$.

See for example [7]. Returning to skew corner-free sets, for a given positive
integer $d$ whose value we will decide upon later, we now let
$V\subset\mathcal{V}_{d}(q,n)$ be the $\mathbb{F}_{q}$-space of polynomials
vanishing on the complement of $X$. Note that the dimension of $V$ satisfies
$\operatorname{dim}(V)\geqslant m_{d}(q,n)-q^{n}+|X|$.

Let $P\in V$ be an element with the support
$\Sigma:=\left\\{x\in\mathbb{F}_{q}^{n}:P(x)\neq 0\right\\}$ of maximum size.
Note that $|\Sigma|\geqslant\operatorname{dim}(V)$ holds, since otherwise
there would exist a nonzero $Q\in V$ vanishing on $\Sigma$. Such a polynomial
$Q$ would generate an element of $V$ with larger support than $P$: indeed,
notice that $(P+Q)(x)=P(x)\neq 0$ holds for every $x\in\Sigma$ and
$(P+Q)(x)=Q(x)\neq 0$ must hold for some $x\not\in\Sigma$.

Now, let $P\in V$ be a polynomial with support $\Sigma$ satisfying

(2) $|\Sigma|\geqslant\operatorname{dim}(V)\geqslant m_{d}(q,n)-q^{n}+|X|.$

For every element $x\in X$, note that there are no distinct elements $y,z\in
C_{x}$ such that $x+z-y\in X$. Indeed, notice that this would yield a skew
corner of the form $(x,y)$, $(x,y+d)$, $(x+d,y^{\prime})$, where $d=z-y$ and
$y^{\prime}$ is some element in the column $C_{x+z-y}$ (which is non-empty if
$x+z-y\in X$). In particular, if $x\in X$ is such that $P(x)\neq 0$, then the
$q^{n}\times q^{n}$ matrix $A$ with rows and columns indexed by the elements
of $\mathbb{F}_{q}^{n}$ and with entries $A_{y,z}=P(x+y-z)$ for
$y,z\in\mathbb{F}_{q}^{n}$ has a very nice property: its the restriction to
the set rows and columns corresponding to the elements of the column $C_{x}$
is a diagonal matrix with non-zero entries on the diagonal. By Lemma 3.1, it
thus follows that

(3) $|C_{x}|\leqslant\operatorname{rank}(A)\leqslant 2m_{d/2}(q,n)$

holds for every $x\in X$ such that $P(x)\neq 0$. On the other hand, by (2),
the number of elements $x\in X$ with $P(x)=0$ is

$|X|-|\Sigma|\leqslant q^{n}-m_{d}(q,n).$

Like in [3], we next note that the quantity $q^{n}-m_{d}(q,n)$ represents the
number of $q$-power-free monomials whose degree is greater than $d$, and these
are in a simple bijection with the set of monomials of degree less than
$(q-1)n-d$. Thus, $q^{n}-m_{d}(q,n)=m_{(q-1)n-d}(q,n)$. For each of these
$x\in X$ with $P(x)=0$, we shall use the trivial bound $|C_{x}|\leqslant
q^{n}$. Putting things together and using the fact that $|\Sigma|\leqslant
q^{n}$, we get that

$\sum_{x\in X}|C_{x}|\leqslant|\Sigma|\cdot
2m_{d/2}(q,n)+m_{(q-1)n-d}(q,n)\cdot q^{n}\leqslant
q^{n}\left(2m_{d/2}(q,n)+m_{(q-1)n-d}\right).$

Picking $d=2(q-1)n/3$, we get that

$\sum_{x\in X}|C_{x}|\leqslant q^{n}\cdot 3m_{(q-1)n/3}(q,n).$

Since

$m_{(q-1)n/3}(q,n)\leqslant\inf_{0<x<1}x^{-(q-1)n/3}(1+x+\ldots+x^{q-1})=q^{(1-c_{q})n}$

(see for example [3]), the conclusion follows.

## References

  * [1] Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam, _Larger Corner-Free Sets from Combinatorial Degenerations_ , 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Dagstuhl, Germany) (Mark Braverman, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 215, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 48:1–48:20.
  * [2] Ernie Croot, Vsevolod F Lev, and Péter Pál Pach, _Progression-free sets in are exponentially small_ , Annals of Mathematics (2017), 331–337.
  * [3] Jordan S Ellenberg and Dion Gijswijt, _On large subsets of with no three-term arithmetic progression_ , Annals of Mathematics (2017), 339–343.
  * [4] Ben Green, _Finite field models in additive combinatorics_ , Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 1–27.
  * [5] Sam Mattheus and Jacques Verstraete, _The asymptotics of $r(4,t)$_, arXiv preprint arXiv:2306.04007, to appear in Annals in Mathematics (2023).
  * [6] Fedor Petrov, _A variant of the corners problem_ , (2023), https://mathoverflow.net/questions/451580/a-variant-of-the-corners-problem/.
  * [7] Fedor Petrov and Cosmin Pohoata, _A remark on sets with few distances in $\mathbb{R}^{d}$_, Proceedings of the American Mathematical Society 149 (2021), 569–571.
  * [8] Kevin Pratt, _On generalized corners and matrix multiplication_ , (2023), arXiv preprint arXiv:2309.03878.
  * [9] I. D. Shkredov, _On a generalization of Szemerédi’s theorem_ , Proc. London Math. Soc. (3) 93 (2006), 723–760.