text:
\begin{document}
\maketitle

\begin{abstract}
A graph $G$ is {\em distinguished} if its vertices are labelled by a
map $\phi: V(G) \longrightarrow \{1,2,\ldots, k\}$ so that no non-trivial
graph automorphism preserves $\phi$.  The distinguishing number of $G$
is the minimum number $k$
necessary for $\phi$ to distinguish the graph.  It
measures the symmetry of the graph.

We extend these definitions to an arbitrary group action of $\Gamma$ on a set $X$.
A labelling $\phi: X \longrightarrow \{1,2,\ldots,k\}$ is
distinguishing if no element of $\Gamma$ preserves $\phi$ except those which
fix each element
of $X$.  The distinguishing number of the group action on $X$
is the minimum $k$ needed for $\phi$ to distinguish the group action.
We show that distinguishing
group actions is a more general problem than distinguishing graphs.

We completely characterize actions of $S_n$ on a set with distinguishing
number $n$, answering an open question of Albertson and Collins.
\end{abstract}

\section{Introduction}

Consider the following dilemma of the considerate roommate.  Returning
home late at night, she would like to
unlock her door without disturbing her roommates either by
turning on a light or by repeatedly trying incorrect
keys in the lock.  One solution is to put different handles
on her keys so that no matter how her keychain is oriented she can identify
each key simply by its shape and its order on the chain.
This leads to a natural question: what is
the minimum number of handles needed to tell her keys apart?

Motivated by this puzzle, Albertson and Collins defined a
distinguished graph to be one
whose vertices are labelled by a function $\phi: V(G) \longrightarrow
\{1, \ldots, k\}$ so that no non-trivial graph automorphism preserves
the labelling \cite{AC}.  From this perspective, the standard keychain
corresponds to a cyclic graph on which each vertex corresponds to a key.
With their definition, Albertson and Collins extended the
puzzle to ask what happens when a keychain is shaped unusually, for
instance like a barbell or like the edges of a cube.

Albertson and Collins
defined the distinguishing number of a graph to be the minimum
number of labels $k$ necessary to distinguish the graph.  In the case of
the cyclic graph, they reproved the classical result
that the cyclic
graphs $C_3$, $C_4$, and $C_5$ require three labels but that the other cyclic
graphs only need two.
In other words, either two or three handles are needed to tell
keys apart by feel, depending on the number of keys on the chain.
Figure \ref{cycles} demonstrates an upper bound for the
distinguishing numbers of $C_5$ and $C_6$.  (The number inside the
vertex $v$ is the labelling $\phi(v)$.)  The reader can enumerate the
possibilities to see that $C_5$ cannot be distinguished with fewer than
three labels.

\begin{figure}[h]
\begin{picture}(350,60)(-55,-30)

\put(35,0){\circle{10}}
\put(32,-3){\small 1}
\put(75,30){\circle{10}}
\put(72, 27){\small 2}
\put(75,-30){\circle{10}}
\put(72, -33){\small 2}
\put(125,20){\circle{10}}
\put(122, 17){\small 3}
\put(125,-20){\circle{10}}
\put(122, -23){\small 1}

\put(39,3){\line(4,3){32}}
\put(39,-3){\line(4,-3){32}}
\put(80,29){\line(5,-1){40}}
\put(80,-29){\line(5,1){40}}
\put(125,15){\line(0,-1){30}}

\put(185,0){\circle{10}}
\put(225,30){\circle{10}}
\put(225,-30){\circle{10}}
\put(275,30){\circle{10}}
\put(275,-30){\circle{10}}
\put(315,0){\circle{10}}
\put(182,-3){\small 1}
\put(222,27){\small 2}
\put(222,-33){\small 2}
\put(272,27){\small 1}
\put(272,-33){\small 2}
\put(312,-3){\small 1}

\put(189,3){\line(4,3){32}}
\put(189,-3){\line(4,-3){32}}
\put(230,30){\line(1,0){40}}
\put(230,-30){\line(1,0){40}}
\put(279,27){\line(4,-3){32}}
\put(279,-27){\line(4,3){32}}
\end{picture}
\caption{Minimally distinguished cyclic graphs} \label{cycles}
\end{figure}

Graphs with the same automorphism group can nonetheless
have different distinguishing numbers.  Instead of asking what the
distinguishing number of a fixed graph is, we may ask which distinguishing
numbers are associated to a fixed group.  In other words, given a
group $\Gamma$ we ask for the set
\[D_{\Gamma} =
\{k: k = D(G) \textup{ for a graph } G \textup{ with } \Aut(G)=\Gamma\}.\]

For instance,
the wreath product $S_2[S_3]$ is the automorphism group of the graph
consisting of two disjoint copies of the complete graph $K_3$.
Figure \ref{different dist nums} shows this and two other graphs with
the same automorphism group and demonstrates that all three have different
distinguishing numbers.  This example disproves a
conjecture in \cite{AC2} that for no group $\Gamma$ is
$D_{\Gamma}=\{2,3,4\}$.  In fact, any graph with automorphism
group $S_2[S_3]$ must have distinguishing number at least $2$ by definition
and no more than $4$ by Theorem \ref{ACK},
and all three possibilities can be realized.

\begin{figure}[h]
\begin{picture}(350,70)(-40,-40)
\put(25,-20){\circle{10}}
\put(45,-20){\circle{10}}
\put(35,20){\circle{10}}
\put(22, -23){\small 1}
\put(42, -23){\small 2}
\put(32, 17){\small 3}
\put(30,-20){\line(1,0){10}}
\put(26,-15){\line(1,4){7.5}}
\put(36,15){\line(1,-4){7.5}}

\put(60,-20){\circle{10}}
\put(80,-20){\circle{10}}
\put(70,20){\circle{10}}
\put(65,-20){\line(1,0){10}}
\put(61,-15){\line(1,4){7.5}}
\put(71,15){\line(1,-4){7.5}}
\put(57,-23){\small 1}
\put(77, -23){\small 2}
\put(67, 17){\small 4}

\put(28,-40){$D(G_1)=4$}

\put(120,-20){\circle{10}}
\put(140,-20){\circle{10}}
\put(160,-20){\circle{10}}
\put(140,20){\circle{10}}
\put(175,-20){\circle{10}}
\put(195,-20){\circle{10}}
\put(215,-20){\circle{10}}
\put(195,20){\circle{10}}
\put(117,-23){\small 1}
\put(137,-23){\small 2}
\put(157,-23){\small 3}
\put(137,17){\small 1}
\put(172,-23){\small 1}
\put(192,-23){\small 2}
\put(212,-23){\small 3}
\put(192,17){\small 2}
\put(138,16){\line(-1,-2){16}}
\put(140,15){\line(0,-1){30}}
\put(142,16){\line(1,-2){16}}
\put(193,16){\line(-1,-2){16}}
\put(195,15){\line(0,-1){30}}
\put(197,16){\line(1,-2){16}}

\put(147,-40){$D(G_2)=3$}

\put(255,-20){\circle{10}}
\put(275,-20){\circle{10}}
\put(295,-20){\circle{10}}
\put(263,0){\circle{10}}
\put(275,0){\circle{10}}
\put(287,0){\circle{10}}
\put(275,20){\circle{10}}
\put(310,-20){\circle{10}}
\put(330,-20){\circle{10}}
\put(350,-20){\circle{10}}
\put(318,0){\circle{10}}
\put(330,0){\circle{10}}
\put(342,0){\circle{10}}
\put(330,20){\circle{10}}
\put(252,-23){\small 1}
\put(272,-23){\small 2}
\put(292,-23){\small 2}
\put(260,-3){\small 2}
\put(272,-3){\small 1}
\put(284,-3){\small 2}
\put(272,17){\small 1}
\put(307,-23){\small 1}
\put(327,-23){\small 2}
\put(347,-23){\small 2}
\put(315,-3){\small 2}
\put(327,-3){\small 1}
\put(339,-3){\small 2}
\put(327,17){\small 2}
\put(272,16){\line(-1,-2){6}}
\put(261,-5){\line(-1,-2){5}}
\put(275,15){\line(0,-1){10}}
\put(275,-5){\line(0,-1){10}}
\put(278,16){\line(1,-2){6}}
\put(289,-5){\line(1,-2){5}}
\put(327,16){\line(-1,-2){6}}
\put(316,-5){\line(-1,-2){5}}
\put(330,15){\line(0,-1){10}}
\put(330,-5){\line(0,-1){10}}
\put(333,16){\line(1,-2){6}}
\put(344,-5){\line(1,-2){5}}

\put(282,-40){$D(G_3)=2$}
\end{picture}
\caption{Three graphs with automorphism group $S_2[S_3]$}
   \label{different dist nums}
\end{figure}

In this paper we extend the notion of distinguishing numbers to
an arbitrary group action on a set.
This definition is quite natural since distinguishing graphs often involves
studying the action of the automorphism group on a single vertex orbit, in
effect considering a more general group action on a particular set of
vertices.

Section \ref{group actions} discusses distinguishing numbers of
general group actions in more
detail.  The distinguishing numbers of some common group actions are
computed, including translations as well as conjugations by $S_n$ on
various sets.  This section also gives
an orbit-by-orbit construction of a distinguishing
labelling for arbitrary group actions, which generalizes an
analogous construction from the theory of distinguishing graphs.
Theorem \ref{n! orbit} completely characterizes group actions on a set
which have distinguishing number $n$ when the group has order $n!$,
proving in this case that  all of the group orbits have size one,
except for one orbit with $n$ elements upon which the group acts as
all possible permutations.

Section \ref{$S_4$ example} shows that distinguishing numbers
of graphs and general group actions are substantively different.  This
section contains a proof
that a faithful $S_4$-action on a set has distinguishing number $2$, $3$, or
$4$ by demonstrating $S_4$-actions with each of these distinguishing numbers.
By contrast, Albertson and Collins showed that no graph has
automorphism group $S_4$ and distinguishing number $3$
in \cite{AC}.

Section
\ref{distinguishing graphs} uses group actions to
compute distinguishing numbers of graphs.  Theorem \ref{trees}
proves that the distinguishing number of a tree
is bounded by its maximum degree and that this bound is sharp.  This
is similar to work in \cite[2.2.4 and 2.2.5]{Ch},
which uses a different approach than
that taken in this paper.  This section also contains Theorem
\ref{complete graph}, which uses Theorem \ref{n! orbit} to prove
a conjecture of \cite{AC} that any graph with automorphism group $S_n$ and
distinguishing number $n$ is either $K_n$ or $\overline{K_n}$ as well as any
number of $1$-orbits.

The author is very grateful to Daniel Isaksen for suggesting the study of
general group actions, to Karen Collins and Michael Albertson for many
helpful conversations, and to the referees for very
useful suggestions.

\section{Distinguishing group actions}\label{group actions}

Any group action on a set can be distinguished, not just that of
the automorphism group on a graph.
In fact these more general
group actions arise frequently, for instance as
the action of the automorphism group of a graph on one of its vertex
orbits.  This highlights the main algebraic difference between
distinguishing
groups and distinguishing graphs: many groups
do not act faithfully while the automorphism group of a graph
always has trivial stabilizer.

In this section we define the distinguishing number of a group action
and compute it for some examples, including translation and conjugation
actions.  We demonstrate two different ways to construct a labelling
orbit-by-orbit and show how these can be used to bound
the distinguishing number by $k$ when the group has order at most $k!$.
The main steps are Theorems \ref{upper bound} and \ref{lower bound},
which generalize an unpublished proof of Albertson, Collins, and Kleitman
\cite{Co}.  In Theorem \ref{n! orbit} we prove a more general version of
a conjecture by Albertson and Collins that characterizes completely
those sets acted on by a group of order $n!$ with distinguishing number $n$.

Let $\Gamma$ be a group which acts on the set $X$.  If $g$ is an element
of $\Gamma$ and $x$ is in $X$ then denote the action of $g$ on $x$
by $g.x$.  Write $\Gamma.x$ for the
orbit containing $x$.  Recall that the
stabilizer of the subset $Y \subseteq X$ is defined to be
\[\Stab_\Gamma(Y)=\{g \in \Gamma: g.y = y \textup{ for all } y \in Y\}.\]
We sometimes omit the subscript and write $\Stab(Y)$.
We also use $\langle g \rangle$ to denote the subgroup of $\Gamma$
generated by $g$.  Assume all groups and sets are finite.

A labelling of $X$ is a map $\phi: X \longrightarrow \{1, 2, \ldots, k\}$.
We say that $\phi$ is
a $k$-distinguishing labelling if the only group elements
that preserve the labelling
are in $\Stab(X)$.  Equivalently, the map $\phi$ is a $k$-distinguishing
labelling
if $\{g: \phi \circ g = \phi\} = \Stab(X)$.  The distinguishing number
$D_\Gamma(X)$ of the set $X$ with a given group action of $\Gamma$
is the minimum $k$ for which there is a $k$-distinguishing labelling.

For example, consider what happens when $S_3$ acts by conjugation
on itself.  There are
three orbits under this action, namely the three conjugacy classes of $S_3$.
Figure \ref{S3 example} shows these orbits with lines between elements of
$S_3$ if the two elements are conjugate.
The stabilizer of
the transposition $(12)$ is the group generated by $(12)$.
Similarly the stabilizer of $(123)$ is the group generated by $(123)$.
Consequently the labelling given by
\[\begin{array}{l}\phi(12) = \phi(123) = 2 \textup{, and} \\
\phi(x)=1 \textup{ otherwise} \end{array}\]
is a $2$-distinguishing labelling of $S_3$
under the conjugation action.  This labelling is shown
in Figure \ref{S3 example}.
Theorem \ref{conjugacy action} generalizes
this example to show that whenever $S_n$ acts on itself by conjugation its
distinguishing number is $2$.

\begin{figure}[h]
\begin{picture}(350,70)(-10,-25)
\put(45,15){$\id$}
\put(50,0){\circle{10}}
\put(47,-3){\small 1}
\put(85,-10){$(12)$}
\put(100,-20){\circle{10}}
\put(97,-23){\small 2}
\put(205,-15){$(13)$}
\put(200,-20){\circle{10}}
\put(197,-23){\small 1}
\put(154,35){$(23)$}
\put(150,30){\circle{10}}
\put(147,27){\small 1}
\put(105,-20){\line(1,0){90}}
\put(104,-17){\line(1,1){43}}
\put(154,27){\line(1,-1){43}}
\put(265,15){$(123)$}
\put(275,0){\circle{10}}
\put(272,-3){\small 2}
\put(340,15){$(132)$}
\put(350,0){\circle{10}}
\put(347,-3){\small 1}
\put(280,0){\line(1,0){65}}

\end{picture}
\caption{$S_3$ acts on itself by conjugation} \label{S3 example}
\end{figure}

The first proposition follows immediately from the definitions.

\begin{proposition} \label{trivial action}
The group $\Gamma$ acts on the set $X$ by fixing each element
if and only if $D_{\Gamma}(X)=1$.
\end{proposition}

The next proposition computes the
distinguishing number when $\Gamma$ acts on itself by translation.

\begin{proposition} \label{translation}
If $\Gamma$ acts on itself by translation then $D_\Gamma(\Gamma)=2$.
\end{proposition}

\begin{proof}
Fix $h_0$ in $\Gamma$ and define the labelling
\[\phi(h) = \left\{ \begin{array}{ll} 2 & \textup{ if } h = h_0
   \textup{, and}\\
    1 & \textup{ otherwise.} \end{array} \right.\]
If $g$ preserves the labelling then $\phi(g.h_0)=\phi(h_0)=2$.
This implies that $g.h_0=h_0$.  Since $g.h_0=gh_0$ the element $g$ must
be the identity.
\end{proof}

The
next lemma is a basic tool to recursively construct distinguishing
labellings.

\begin{lemma} \label{orbit induction}
Fix an orbit $O$ under the action of $\Gamma$ on $X$.
Let $\phi_1$ be a $(k_1)$-distinguishing labelling of $O$ under the action of
$\Gamma$ and let $\phi_2$ be a $(k_2)$-distinguishing labelling of $X \backslash
O$ under the action of $\Gamma$.
The labelling $\phi$ defined by $\phi|_O = \phi_1$ and $\phi|_{X\backslash O}
= \phi_2$ is a $\max \{k_1,k_2\}$-distinguishing of
$X$ under the action of $\Gamma$.
\end{lemma}

\begin{proof}
If $g$ preserves the labelling $\phi$ then
$g$ preserves both $\phi_O$ and $\phi_{X \backslash O}$.  Consequently
$g$ is in the subgroup $\Stab(O) \cap \Stab(X \backslash O)$
and so $g$ is in $\Stab(X)$.
\end{proof}

This gives a numerical condition for $2$-distinguishability.

\begin{corollary} \label{relatively prime}
Suppose $\Gamma$ acts on $X$ and $O_1$ and $O_2$ are two orbits under this action.
If $|\Gamma|/|O_1|$ is relatively prime to $|\Gamma|/|O_2|$ then $D_\Gamma(X)=2.$
\end{corollary}

\begin{proof}
Choose $x_1 \in O_1$ and $x_2 \in O_2$.
Define a labelling $\phi: X \longrightarrow \{1,2\}$ by setting
$\phi(x_1) = \phi(x_2) = 2$ and $\phi(x) = 1$
for all other $x$.  If $g$ preserves $\phi$ then it satisfies
\[\phi(g . x_1) = 2 = \phi(g . x_2).\]
Since $g.x_i \in O_i$ and $x_i$ is the only element of $O_i$ labelled by $2$,
the action of $g$
must fix each of $x_1$ and $x_2$.
In other words $g$ is in $\Stab(x_1)
\cap \Stab (x_2)$.  The cardinality of these stabilizer subgroups
is given by $|\Stab(x_i)| = |\Gamma|/|O_i|$ as shown in
\cite[1.5.1 and 1.2.2]{L}.  These cardinalities are
relatively prime by hypothesis so the intersection of the stabilizers
is the identity.  Consequently $\phi$ is a
$2$-distinguishing labelling.
\end{proof}

This result can be used to distinguish the action of $S_n$ on
itself by conjugation since relatively prime orbits can be constructed
in that case.

\begin{theorem} \label{conjugacy action}
Let $X$ be the set of permutations $S_n$ with the group action of $S_n$
upon $X$ given by conjugation.  Then $D_{S_n}(S_n) = 2$.
\end{theorem}

\begin{proof}
The orbits of $S_n$ acting on itself by conjugation are the
conjugacy classes of $S_n$ and are characterized by cycle type, that is
by partitions of $n$ (see \cite[2.3 page 18]{FH}).

One orbit corresponds to the cycle type of the permutation $(1 2 \cdots n)$.
The number of $n$-cycles is $(n-1)!$ since each $n$-cycle $\sigma$
is determined uniquely by a sequence $(\sigma^1 (1),\sigma^2 (1), \ldots,
\sigma^n (1))$
which has $\sigma^n(1)=1$ and which permutes the other $n-1$
elements.  Consequently the stabilizer of $(1 2 \cdots n)$ has size
$\frac{n!}{(n-1)!} = n$.

Another orbit corresponds to the cycle type of
$(1)(2 \cdots n)$, which fixes one element and has an $n-1$ cycle.  This
orbit has size $n (n-2)!$ since there are $n$ choices for the fixed element
and $(n-2)!$ ways to choose an $n-1$ cycle.
Consequently the stabilizer of $(1)(2 \cdots n)$ has size
$\frac{n!}{n(n-2)!}=n-1$.

Since $n$ and $n-1$ are relatively prime,
this group action is $2$-distinguishable by Corollary \ref{relatively prime}.
\end{proof}

The next lemma can be
used to construct distinguishing labellings by looking at orbits
under stabilizer subgroups.

\begin{lemma} \label{orbit by orbit}
Fix an action of $\Gamma$ on $X$ and let $X'$ be a subset
of $X$ with $\Gamma.x \neq \Gamma.y$ whenever $x$ and $y$ are two distinct elements
in $X'$.  If $\phi_1$ is a
$(k-1)$-distinguishing labelling of $X \backslash X'$ under the action
of the subgroup $\Stab(X')$ then the map
\[  \phi(u) = \left\{ \begin{array}{ll}
         \phi_{1}(u) & \textup{ if } u \notin X' \textup{, and}\\
         k  & \textup{ if } u \in X' \end{array} \right. \]
is a $k$-distinguishing labelling of $X$ under the action of $\Gamma$.
\end{lemma}

\begin{proof}
If $g$ preserves the labelling $\phi$ then both $\phi_1 \circ
g = \phi_1$ and
$\phi(g.x)=k$ for each $x$ in $X'$.  No two elements in $X'$
lie in the same $\Gamma$-orbit and so $g.x = x$ for each $x$ in $X'$.
Consequently $g$ is in $\Stab(X')$.
Moreover the labelling $\phi_1$
distinguishes $X \backslash X'$ under $\Stab(X')$ and so $g$ must
also be in $\Stab(X \backslash X')$.  Consequently $g$ is in
$\Stab(X)$.
\end{proof}

We use this lemma to construct a distinguishing labelling
for the action of $\Gamma$ on $X$ using the following recursive algorithm.

\medskip

\begin{construction} \label{algorithm}
\hspace{2em}\\

\vspace{-.6cm}
\begin{enumerate}
\item Initialize $i=1$ and set $\phi(x)=1$ for all $x$ in $X$.
Let $\Gamma_1=\Gamma$ and  $X_1=X$.
\item While $\Gamma_i \neq \Stab(X_i)$ do
\begin{enumerate}
\item \label{defn sets}
  Choose a subset $X_{i+1}'$ of $X_i$ that contains a unique element
from each nontrivial $\Gamma_i$-orbit in $X_i$, namely
so that the intersection $|X_{i+1}' \cap \Gamma_i.x| = 1$
for each $x$ in $X_i$ such that $\Gamma_i.x$ has at least two elements.

\item \label{big step} Label the elements of $X_{i+1}'$ with $i+1$,
so $\phi(x)=i+1$ for each $x$ in $X_{i+1}'$.
\item Let $X_{i+1} = X_i\backslash X_{i+1}'$ and let $\Gamma_{i+1} =
  \Stab_{\Gamma_i}(X_{i+1}')$.
\item Increment $i$ by $1$.
\end{enumerate}
\end{enumerate}
\end{construction}

Figure \ref{construction example} gives an example of how this works
when the set $X$ is the set of vertices of the
given graph and the group $\Gamma$ consists of all graph automorphisms.
In this case the algorithm
terminates after the loop is iterated three times.  Comparing the
outcome to Figure \ref{different dist nums}
we observe that this algorithm need not
give a minimal distinguishing labelling.

\begin{figure}[h]
\begin{picture}(350,80)(-55,-30)
\multiput(5,0)(17,0){6}{\circle{10}}
\multiput(22,51)(51,0){2}{\circle{10}}
\multiput(19,47)(51,0){2}{\line(-1,-3){14}}
\multiput(22,46)(51,0){2}{\line(0,-1){41}}
\multiput(25,47)(51,0){2}{\line(1,-3){14}}
\multiput(19,-3)(17,0){5}{\small 1}
\put(19,48){\small 2}
\put(70,48){\small 1}
\put(2,-3){\small 2}
\put(12,-25){First Iteration}

\multiput(124,0)(17,0){6}{\circle{10}}
\multiput(141,51)(51,0){2}{\circle{10}}
\multiput(138,47)(51,0){2}{\line(-1,-3){14}}
\multiput(141,46)(51,0){2}{\line(0,-1){41}}
\multiput(144,47)(51,0){2}{\line(1,-3){14}}
\multiput(155,-3)(17,0){3}{\small 1}
\put(138,48){\small 2}
\put(189,48){\small 1}
\put(121,-3){\small 2}
\put(138,-3){\small 3}
\put(206,-3){\small 3}
\put(125,-25){Second Iteration}

\multiput(243,0)(17,0){6}{\circle{10}}
\multiput(260,51)(51,0){2}{\circle{10}}
\multiput(257,47)(51,0){2}{\line(-1,-3){14}}
\multiput(260,46)(51,0){2}{\line(0,-1){41}}
\multiput(263,47)(51,0){2}{\line(1,-3){14}}
\multiput(274,-3)(17,0){2}{\small 1}
\put(257,48){\small 2}
\put(308,48){\small 1}
\put(240,-3){\small 2}
\put(257,-3){\small 3}
\put(325,-3){\small 3}
\put(308,-3){\small 4}
\put(248,-25){Third Iteration}
\end{picture}
\caption{Constructing a $4$-distinguishing labelling} \label{construction
example}
\end{figure}

The following uses Lemma \ref{orbit by orbit} to
confirm that this  produces a
distinguishing labelling.

\begin{proposition} \label{construction}
Construction \ref{algorithm} terminates after $k-1$ iterations
and produces a
$k$-distinguishing labelling $\phi$ of $X$, for some finite $k$.
\end{proposition}

\begin{proof}
Since $X_i \subsetneq X_{i-1}$ the algorithm terminates after at most $|X|$
iterations.  We induct on $k$.  When
$\Gamma=\Stab(X)$ the algorithm uses no iterations and the
map $\phi$ is trivially a $1$-distinguishing labelling.
Assume that any labelling produced when the algorithm requires $k-2$
iterations is a $k-1$-distinguishing labelling.

Suppose  $\phi$ is produced when the algorithm uses
$k-1$ iterations.  By construction, the element $x$ in $X$ is
labelled $\phi(x)=i>1$ if and only if $x$
is in $X_i'$.  Thus $\phi$  is a $k$-labelling.

Furthermore, the set $X_2'$ has no more than one element from each
$\Gamma$-orbit, by construction.  The restriction  $\phi|_{X_2}$
is a $k-1$-distinguishing labelling under the action of $\Gamma_2$, by
the inductive hypothesis.   By Lemma \ref{orbit by orbit},
the map $\phi$ is a $k$-distinguishing labelling.

\end{proof}

The construction in fact guarantees that there is a set of $k$ nested
orbits under successively smaller stabilizer subgroups.

\begin{theorem} \label{upper bound}
Fix a $k$-distinguishing labelling $\phi$, groups $\{\Gamma_i\}$, and
sets $\{X_i\}$ produced by an implementation of Construction \ref{algorithm}.
There exists a subset $\{y_{1}, \ldots, y_{k}\}$ in $X$ such that
\begin{enumerate}
\item $\phi(y_i) =i$ for each $i$,
\item $y_{i+1}$ is in $\Gamma_{i-1}.y_{i}$ for each $i$ from $2$ to $k-1$,
  and $y_1$ is in $\Gamma_{k-1}.y_k$.
\end{enumerate}
\end{theorem}

\begin{proof}
The algorithm uses $k-1$ iterations so the groups
satisfy $\Gamma_{k-1} \neq \Stab(X_{k-1})$ and $\Gamma_k = \Stab(X_k)$.
This means there is an element $y_1$ in $X_k$ whose orbit $\Gamma_{k-1}.y_1$
has at least two elements.  Note that $\phi(y_1) = 1$ by construction.
Also by construction, the orbit $\Gamma_{k-1}.y_1$ intersects $X_k'$ in
a unique element $y_k$, and $y_k$ is labelled $\phi(y_k)=k$.

Assume that $\{y_i, y_{i+1}, \ldots, y_k, y_1\}$
have been chosen to satisfy the hypotheses.  In particular, the orbit
$\Gamma_{i-1}.y_i$ has at least two elements.  Since
$\Gamma_{i-2} \supset \Gamma_{i-1}$ the orbit $\Gamma_{i-2}.y_i$ also
has at least two elements and so this orbit intersects $X_{i-1}'$
in a unique element $y_{i-1}$.  By construction
 $\phi(y_{i-1})=i-1$
and $\Gamma_{i-2}.y_{i-1}=\Gamma_{i-2}.y_i$.  Induction completes the
proof.
\end{proof}

Together with the coset formula for group orders,
the construction guarantees a lower
bound on the size of orbits under successively smaller stabilizer
subgroups.  This bound generalizes the main point of an earlier construction
of Albertson, Collins, and Kleitman in \cite{AC2}
whose proof is unpublished \cite{Co}.

\begin{theorem}\label{lower bound}
Fix a $k$-distinguishing labelling $\phi$, groups $\{\Gamma_i\}$, and
sets $\{X_i\}$ produced by an implementation of Construction \ref{algorithm}.
If $\{y_1, \ldots, y_j\}$ is a subset of $X$ such that
\begin{enumerate}
\item $\phi(y_i)=i$ for each $i$,
\item $y_{i+1}$ is in $\Gamma_{i-1}.y_{i}$ for each $i$ from $2$ to $j-1$,
  and $y_1$ is in $\Gamma_{j-1}.y_j$,
\end{enumerate}
then $\displaystyle |\Gamma| \geq |\Gamma_1.y_{2}| |\Gamma_{2}.y_{3}| \cdots
    |\Gamma_{j-1}.y_{j}||\Gamma_{j}.y_1| |\Stab_{\Gamma_{j}}(y_{1})|$.
\end{theorem}

\begin{proof}
Recall that whenever a group $\Gamma$ acts on a set $X$ and $y$ is in $X$,
the orders satisfy
\[|\Gamma| = |\Gamma.y| \cdot |\Stab_\Gamma(y)|\]
(see \cite[1.5.1 and 1.2.2]{L}).
Observe that for each $i \neq 1$ the
group $\Stab_{\Gamma_{i-1}}(y_{i}) \supseteq \Gamma_{i}$
since $\Gamma_i = \bigcap_{y \in X_i'} \Stab_{\Gamma_{i-1}}(y)$ by
definition.

Together, these identities give the following:
\[\begin{array}{rl} \label{bound}
  |\Gamma| &= |\Gamma.y_{2}| |\Stab_{\Gamma}(y_{2})| \\
  &\geq |\Gamma_{}.y_{2}| |\Gamma_{2}| \\
  &= |\Gamma_{}.y_{2}| |\Gamma_{2}.y_{3}| |\Stab_{\Gamma_{2}}(y_{3})| \\
  &\cdots \\
  &= |\Gamma_{}.y_{2}| |\Gamma_{2}.y_{3}| \cdots
    |\Gamma_{j-1}.y_j| |\Gamma_j.y_1||\Stab_{\Gamma_j}(y_1)|. \end{array} \]
Since $\Gamma = \Gamma_{1}$ this proves the claim.
\end{proof}

The next corollary uses this result and a lower bound for each
$|\Gamma_{i-1}.y_{i}|$ to bound $|\Gamma|$.

\begin{corollary} \label{bound size of set}
Fix a $k$-distinguishing labelling $\phi$, groups $\{\Gamma_i\}$, and
sets $\{X_i\}$ produced by an implementation of Construction \ref{algorithm}.
If $|\Gamma| \leq m!$ and the subset
$\{y_{1}, \ldots, y_{j}\}$ satisfies
\begin{enumerate}
\item $\phi(y_i)=i$ for each $i$,
\item $y_{i+1}$ is in $\Gamma_{i-1}.y_{i}$ for each $i$ from $2$ to $j-1$,
  and $y_1$ is in $\Gamma_{j-1}.y_j$,
\end{enumerate}
then $j \leq m$ and $|\Gamma_{i-1}.y_{i}| \geq j-i+2$ for each $i$ from
$2$ to $j$.
\end{corollary}

\begin{proof}
We first show that the set $\Gamma_{i-1}.y_{i}$ contains
$\{y_{i}, y_{i+1}, \ldots, y_{j}, y_1\}$ for each $i$.  Indeed, the orbit
$\Gamma_{i-1}.y_{i} = \Gamma_{i-1}.y_{i+1}$ by definition.
Since the subgroup $\Gamma_{i-1} \supset
\Gamma_{i}$ it follows that $\Gamma_{i-1}.y_{i+1} \supset
\Gamma_{i}.y_{i+1}$.  (The containment  $\Gamma_{i-1}.y_{i+1} \supsetneq
\Gamma_{i}.y_{i+1}$ is proper because $\Gamma_i$ fixes $y_i$.)
Consequently, the claim need only hold for $\Gamma_{j-1}.y_{j}$,
which it does by hypothesis.
Thus, each orbit $\Gamma_{i-1}.y_{i}$ contains at least
$j-i+2$ elements.

By Theorem \ref{lower bound}
\[ |\Gamma| \geq |\Gamma_{1}.y_{2}| |\Gamma_{2}.y_{3}| \cdots
    |\Gamma_{j-1}.y_j| |\Gamma_j.y_1|
    |\Stab_{\Gamma_j}(y_1)|\]
so $|\Gamma| \geq j!$.  By hypothesis $m! \geq |\Gamma|$ so $j$ is at
most $m$.
\end{proof}

This corollary relates $|\Gamma|$ to the number of iterations of Construction
\ref{algorithm} and thus to the distinguishing number.

\begin{corollary} \label{ACK bound}
If $|\Gamma|$ is at most $ k!$ then $D_\Gamma(X)$ is at most $k$.
\end{corollary}

\begin{proof}
Let $\phi$ be an $j$-distinguishing labelling produced by Construction \ref{algorithm}.
By Theorem \ref{upper bound}
there exist $j$ elements satisfying the conditions of
Corollary \ref{bound size of set} so $j$ is at most $k$.
\end{proof}

This construction actually distinguishes
each orbit of a group action separately.

\begin{corollary} \label{single orbit}
Suppose $|\Gamma| \leq k!$.
If $\Gamma$ acts on $X$ and $O$ is any orbit of this action then $O$
can be distinguished under the action of $\Gamma$ with at most $k$ labels.
\end{corollary}

\begin{proof}
Apply Corollary \ref{ACK bound} to the action of $\Gamma$ on $O$.
\end{proof}

The next result
was originally formulated by Albertson, Collins, and Kleitman
for graphs.

\begin{corollary} \label{ACK}
(Albertson, Collins, and Kleitman) A graph $G$ with $|\Aut(G)| \leq k!$ has
distinguishing number $D(G) \leq k$.
\end{corollary}

\begin{proof}
Apply Corollary \ref{ACK bound} to the action of the automorphism group
of $G$ on the set of vertices of the graph $G$.
\end{proof}

The following theorem completely characterizes group actions for which
$|\Gamma|=n!$ and
the distinguishing number is $n$.  It generalizes a conjecture of
Albertson and Collins for graphs that is proven in Theorem \ref{complete
graph}.

The proof counts cardinalities to show that the set guaranteed by
Theorem \ref{upper bound}
must in fact consist of $n$ elements with an action of
all $n!$ permutations.  It then demonstrates that any other non-trivial
orbit would decrease the distinguishing number.

Note that this result is stronger than
the analogous statement for graphs given in Theorem \ref{complete graph},
because the edges in a graph constrain the way that the automorphism
group can act.  General group actions do not have this added structure.

\begin{theorem} \label{n! orbit}
If $|\Gamma|=n!$ and $\Gamma$ acts on $X$ with distinguishing number $n$ then
there is an orbit $\Gamma.x$ in $X$ with $n$ elements upon which $\Gamma$ acts
as the set of all possible permutations.  The rest of the orbits in $X$
have size $1$.
\end{theorem}

\begin{proof}
If the distinguishing number of $\Gamma$ on $X$ is $n$ then by Lemma
\ref{orbit induction} there exists at
least one orbit $\Gamma.x$ for which $D_\Gamma(\Gamma.x)$ is at least $n$.  In particular
the map $\phi$ given by implementing Construction \ref{algorithm} for the
action of $\Gamma$ on $\Gamma.x$
is an $n$-distinguishing labelling.  (Corollary \ref{single orbit}
shows that $\phi$ is at most $n$-distinguishing.  If $\phi$
used fewer than $n$ labels then $D_\Gamma(\Gamma.x)$ would be less than
$n$.)

We show first that $\Gamma.x$ consists of $n$ elements.
By Theorem \ref{upper bound}
we can find $\{y_1, \ldots, y_n\}$ in $\Gamma.x$ satisfying both
$y_{i+1} \in \Gamma_{i-1}.y_{i}$ and $\phi(y_i) = i$.  By Theorem
\ref{lower bound} the inequality
\[ |\Gamma| \geq |\Gamma_1.y_2| |\Gamma_2.y_3| \cdots |\Gamma_{n-1}.y_n|
   |\Gamma_{n}.y_1|\]
holds.  Corollary \ref{bound size of set} proved that
 $\Gamma_{i-1}.y_i \supseteq \{y_i,y_{i+1},
\ldots, y_n, y_1\}$ and so
$|\Gamma| \geq n!$.  Because $|\Gamma|=n!$ each orbit $\Gamma_{i-1}.y_{i}
= \{y_i,y_{i+1},
\ldots, y_n, y_1\}$ must have exactly $n-i+2$ elements, and
$\Gamma_n.y_1=\{y_1\}$.  In particular
 note that $\Gamma_1.y_2 = \Gamma.x = \{y_1, \ldots, y_n\}$.

We now show that $\Gamma$ acts on this orbit by all possible
permutations.  To begin we prove that $\Gamma_i =
\Stab_{\Gamma}(y_2, \ldots, y_{i-1})$
and that $|\Gamma_i|=(n-i+1)!$.  This is true by hypothesis when $i$ is one.
Assume the claim holds for $\Gamma_{i-1}$.  By the coset formula,
\[|\Gamma_{i-1}| = |\Gamma_{i-1}.y_i| \cdot |\Stab_{\Gamma_{i-1}}(y_i)|.\]
Since $|\Gamma_{i-1}.y_i| = n-i+2$
this implies that $|\Stab_{\Gamma_{i-1}}(y_i)| = (n-i+1)!$.
By definition $\Gamma_{i} \subseteq \Stab_{\Gamma_{i-1}}(y_i)$.
When Construction \ref{algorithm} is
used for the action of $\Gamma_{i}$
on $\Gamma_{i}.y_{i+1}$, the algorithm
terminates after $n-i$ iterations.  Theorem
\ref{lower bound} shows that $|\Gamma_{i}| \geq (n-i+1)!$ and so
in fact
$\Gamma_{i} = \Stab_{\Gamma_{i-1}}(y_i)$. By induction
$\Stab_{\Gamma_{i-1}}(y_i)=\Stab_{\Gamma}(y_2, \ldots, y_{i})$.

If $g$ and $h$ in $\Gamma$ act the same on the orbit $\Gamma.x$
then $g^{-1}h$ must be in $\Stab_{\Gamma}(y_1, \ldots,y_n)$.

Since $\Stab_{\Gamma}(y_1, \ldots, y_{n})$
has only one element this means $g^{-1}h$ is the identity.
In other words, each of the
$n!$ elements in $\Gamma$ acts differently upon $\Gamma.y_1 =
\{y_1, \ldots, y_n\}$.  Since each element of $\Gamma$ permutes $\{y_1,
\ldots, y_n\}$ the group acts as all possible permutations
upon this $n$-element orbit.

Finally we confirm that every orbit other than $\Gamma.x$ is a $1$-orbit.
Suppose $O$ is any orbit other than $\Gamma.x$ and fix $x'$ in $O$.
Define a labelling of $O$ by
\[\phi_1(y) = \left\{ \begin{array}{rl} 2 & \textup{ if } y = x'
   \textup{, and}\\
    1 & \textup{ otherwise.} \end{array} \right.\]
The group elements that preserve this labelling are precisely those of
$\Stab_{\Gamma}(x')$.
Let $\phi_2$ be a $k$-distinguishing labelling of $X \backslash O$
under the action of $\Stab_{\Gamma}(x')$.  If $g$ preserves $\phi_2$ then $g$ is
in $\Stab_{\Gamma}(X \backslash O) \cap \Stab_{\Gamma}(x') = \langle \id \rangle$,
since $\Stab_{\Gamma}(X \backslash O)$ is contained in $\Stab_{\Gamma}(\Gamma.x)$ which
is itself trivial.  This means that the labelling
\[\phi(y) = \left\{ \begin{array}{rl} \phi_1(y) & \textup{ if } y \in O
\textup{, and}\\
    \phi_2(y) & \textup{ if } y \in X \backslash O \end{array} \right.\]
distinguishes $X$ under the action of $\Gamma$ with at most $k$ labels.
If $O$ has at least two elements then the relation
$|\Gamma|=|O||\Stab_{\Gamma}(x')|$ shows that
$|\Stab_{\Gamma}(x')| < n!$.  By Corollary \ref{ACK bound} the set
 $X \backslash O$ can be distinguished under the action of $\Stab_{\Gamma}(x')$ with
at most $k \leq n-1$ labels.  This would mean
that $X$ is $n-1$-distinguishable, which contradicts the hypothesis.
\end{proof}

\section{Distinguishing numbers for $S_4$ actions}\label{$S_4$ example}

Albertson and Collins showed that if a graph has automorphism group $S_4$
then its distinguishing number is either $2$ or $4$ (see
\cite{AC}).  We demonstrate
here that the analogous statement for $S_4$-actions on sets is false
even when restricted to faithful $S_4$-actions.  This shows that
the problem of distinguishing group actions is more general than the
problem of distinguishing graphs.

The choice of $X$ with $D_{S_4}(X)=3$ was inspired by a conversation with
Daniel Isaksen.

\begin{theorem}
If $S_4$ acts on $X$ then the distinguishing number $D_{S_4}(X)$ is
either $1$, $2$, $3$, or $4$.  If $S_4$ acts faithfully on $X$ then
$D_{S_4}(X)$ is either $2$, $3$, or $4$.
\end{theorem}

\begin{proof}
The distinguishing number of an $S_4$-action is $1$, $2$, $3$, or $4$ by
Corollary \ref{ACK bound}.

The trivial $S_4$-action on the one-element set has distinguishing number
$1$.

If $S_4$ acts on itself by translation,
its distinguishing number is $2$ by Proposition \ref{translation}.

When $S_4$ acts on the $4$-element set by all
possible permutations its distinguishing number is $4$, by
Theorem \ref{n! orbit}.

Let $X$ be graph whose vertex set is
the conjugacy class of the permutation $(1234)$ and whose edge set
consists of $(v,v')$ such that the permutation $v$ is the inverse of
$v'$.  The graph $X$ is given in Figure \ref{graph of conjugacy}, showing
both a labelling $\phi$ indicated by the numbers within the vertices and
the permutation corresponding to each vertex.
Let $S_4$ act on $X$ by conjugation.  (This action does consist of
graph automorphisms since conjugation preserves inverses.)
Figure \ref{graph of conjugacy}
shows a $3$-distinguishing labelling of $X$ under this action.
The rest of this proof verifies that no $2$-labelling $\phi'$
distinguishes $X$ and so in fact $D_{S_4}(X)=3$.

\begin{figure}[h]
\begin{picture}(350,60)(-20,0)
\put(100,10){\circle{10}}
\put(100,50){\circle{10}}
\put(300,10){\circle{10}}
\put(300,50){\circle{10}}
\put(200,10){\circle{10}}
\put(200,50){\circle{10}}

\put(97,7){\small 1}
\put(197,7){\small 2}
\put(297,7){\small 3}
\put(97,47){\small 2}
\put(197,47){\small 3}
\put(297,47){\small 1}

\put(110,50){(1234)}
\put(110,10){(1432)}
\put(210,50){(1243)}
\put(210,10){(1342)}
\put(310,50){(1324)}
\put(310,10){(1423)}

\put(100,15){\line(0,1){30}}
\put(200,15){\line(0,1){30}}
\put(300,15){\line(0,1){30}}
\end{picture}
\caption{The graph $X$ with a $3$-distinguishing labelling}\label{graph of conjugacy}
\end{figure}

Suppose $\phi'$ gives both vertices of a component the same label for
 two different components, say without
loss of generality that $\phi'((1243))=\phi'((1342))$ and $\phi'((1324))=
\phi'((1423))$.  Then the action of $(13)(24)$ on $X$ preserves each
component, exchanging each of these pairs while fixing the first component,
and so $\phi'$ does not distinguish $X$.  We assume $\phi'$ does not label
two components in this way.

Now suppose both vertices of one component share the same label, say
without loss of generality $\phi'((1234))=\phi'((1432))$.  The action of
each of $(13)$ and $(24)$ exchanges the vertices $(1234)$ and $(1432)$ and
exchanges the other two components, switching the components in the
two possible ways.  Thus $\phi'$ cannot distinguish the graph.

Finally, suppose $\phi'$ gives a different label to the two elements of
each component, and say without loss of generality that
$\phi'((1234))=\phi'((1243))=\phi'((1324))$ and
$\phi'((1432))=\phi'((1342))=\phi'((1423))$.  Then the action of
$(14)(12)$ on
$X$ cyclically permutes the three components while preserving the
labelling, so $\phi'$ does not distinguish $X$.
\end{proof}

Albertson and Collins conjectured that if a graph $G$ has automorphism group
$S_n$ and $D(G) \neq n$ then in fact $D(G) \leq \frac{n}{2}$ as long as
$n$ is at least $4$.  The previous theorem shows that this is false for
general group actions.  However, suppose the group action of $\Gamma$ on
$X$ is
faithful, namely $\Stab_{\Gamma}(X)=\langle id \rangle$.
For example, if $G$ is a graph then its automorphism group
acts faithfully on $G$ because only the identity automorphism
fixes each vertex.

We ask the following.

\begin{question}
Do there exist faithful
group actions of $S_n$ on $X$ with $D_{S_n}(X)=n-1$ for arbitrarily
large $n$?
\end{question}

\section{Distinguishing graphs using orbits} \label{distinguishing graphs}

In this section we apply the theory developed for distinguishing
general group actions to graphs.
Combining the general theory with properties of graphs that are
invariant under automorphism, for instance distance or degree, permits
these results to be extended.  In Theorem \ref{trees} we
distinguish trees.  In Theorem \ref{complete graph}
we describe all graphs with automorphism group $S_n$ and distinguishing
number $n$.

Cheng provided a different proof of Theorem \ref{trees} in
\cite[2.2.4 and 2.2.5]{Ch}
as well as an algorithm to compute the distinguishing number of
trees.

\begin{theorem} \label{trees}
If $T$ is a tree with maximum degree $d \geq 2$ then $D(T)$ is at most $d$.
Otherwise $T$ is either a tree with one vertex and $D(T)=1$ or a tree
with two vertices and $D(T)=2$.
\end{theorem}

\begin{proof}
The proof inducts on the number of vertex orbits in $T$.
Suppose that $T$ consists of a single vertex orbit.
Each graph automorphism
preserves the degree of its vertices, in the sense that $\deg(v) =
\deg(\sigma v)$ for each vertex $v$ and automorphism $\sigma$.  Since
all vertices in $T$ are in the same orbit, they must all be leaves.
Consequently $T$ consists of either a single vertex or a
single edge between two vertices, and $D(T)$ is as given.

Now assume $T$ has at least two orbits and let $d$ be the maximum degree
of $T$.  Let $O_v$ be any vertex orbit in $T$ which contains a leaf.
This means that all of
the vertices in $O_v$ are leaves.  Write $T'$ for the subgraph induced
by $V(T) - O_v$.  The graph $T'$ is also a tree since no internal vertices
were removed from $T$.

If $\sigma$ is a graph automorphism of $T$ then $\sigma O_v = O_v$ by
definition.  Let $\Stab(T')$ be the stabilizer of $T'$ in $\Aut(T)$.
Let $\sigma$ be in $\Stab(T')$ and choose an edge $uw$
from a vertex $u$ in $T'$ to a vertex $w$ in $O_v$.  The automorphism
$\sigma$ sends the edge $uw$ to $(\sigma u) (\sigma w) = u (\sigma w)$.  This
means that the stabilizer of $T'$ permutes vertices in $O_v$ with a shared
neighbor.

Suppose $\phi$ is a distinguishing
labelling of $T'$.  We
extend $\phi$ to $T$ by requiring that for each vertex $u$ in $T'$
that is adjacent to a vertex in $O_v$, the neighbors $N_T(u) \cap O_v$ are
labelled distinctly.  This requires at most $d$ labels, where $d$ is
the maximum degree of $T$.
By Lemma \ref{orbit induction}
the map $\phi$ is a $\max\{d, D(T')\}$-distinguishing of $T$.
Since $T$ has at least two vertex orbits
it has an internal vertex, so $d$ is at least $2$.
The maximum degree of the subtree $T'$ is no greater than $d$, and hence
the result holds by induction on the number of vertex orbits.
\end{proof}

The tree constructed by attaching $i$ leaves and $d-i$ paths of
different lengths to a central root has distinguishing number
$i$ and maximum degree $d$.  Figure \ref{tree example} shows such a tree
when $i$ is $3$ and $d$ is $5$.  This shows that the bound in Theorem
\ref{trees} is sharp.

\begin{figure}[h]
\begin{picture}(348,50)(-85,-25)
\put(85,0){\circle{10}}
\multiput(25,-20)(0,20){3}{\circle{10}}
\multiput(145,15)(60,0){2}{\circle{10}}
\multiput(145,-15)(60,0){3}{\circle{10}}
\multiput(150,-15)(60,0){2}{\line(1,0){50}}
\put(22,-23){\small 3}
\put(22,-3){\small 2}
\put(22,17){\small 1}
\put(82,-3){\small 1}
\multiput(142,12)(60,0){2}{\small 1}
\multiput(142,-18)(60,0){3}{\small 1}

\put(150,15){\line(1,0){50}}
\put(80,0){\line(-1,0){50}}
\put(80,1.5){\line(-3,1){50}}
\put(80,-1.5){\line(-3,-1){50}}
\put(90,1){\line(4,1){50}}
\put(90,-1){\line(4,-1){50}}
\end{picture}
\caption{A tree with distinguishing number $3$ and maximum degree $5$}
 \label{tree example}
\end{figure}

The next result characterizes graphs whose automorphism group is $S_n$
and whose distinguishing number is $n$.  This proves a conjecture
in \cite{AC}.

\begin{theorem} \label{complete graph}
If $\Aut(G)=S_n$ and $D(G)=n$ then one orbit of $G$ is a copy of $K_n$
or $\overline{K_n}$ and the rest are $1$-orbits.
\end{theorem}

\begin{proof}
Theorem \ref{n! orbit} showed that $G$ has one vertex orbit $O$ with
$n$ elements upon which $\Aut(G)$ acts as all possible permutations.
All the other vertex orbits of $G$ are $1$-orbits.

If $u$ and $v$ are two vertices in $O$ with an edge between them then
$(\sigma u)(\sigma v)$ will be an edge for each $\sigma$ in $\Aut(G)$.
Since the group of all permutations acts doubly
transitively
on the $n$ element set, there exists $\sigma$ with $\sigma u =u'$
and $\sigma v =v'$ for each pair of vertices $u'$,$v'$.  If $O$ does
not induce $\overline{K_n}$ then it induces
$K_n$.
\end{proof}


text:
\subsection{Proof of Theorem \ref{thm:regstat}}

Standard calculations (see, e.g., \cite{Das18, Das19}) show that the gradient and Hessian of the empirical log-likelihood can be written as:
\begin{equation}\label{eqn:reggrad}
\nabla l_n(\vec{\Omega}) = -\frac1n \sum_{i=1}^n  \left(\vec{x}^{(i)}y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}( \vec{x}^{(i)}\vec{\Omega}, 1, S)}[\vec{x}^{(i)} z^{(i)}]\right)
\end{equation}
\begin{equation}\label{eqn:reghess}
H(\vec{\Omega}) \defeq \nabla^2 l_n(\vec{\Omega}) = \frac1n \sum_{i=1}^n \Cov_{z^{(i)} \sim \mathcal{N}( \vec{x}^{(i)}\vec{\Omega}, 1, S)}[\vec{x}^{(i)} z^{(i)}, \vec{x}^{(i)} z^{(i)}]
\end{equation}
From (\ref{eqn:reghess}), since $H(\vec{\Omega}) \succeq 0$, it is clear that $l_n$ is convex for arbitrary choices of $\vec{x}^{(1)}, \dots, \vec{x}^{(n)}$.
\ignore{
Also, note that the Hessian of $l_n$ and $\bar{\ell}$ (from (\ref{eqn:popl})) are identical because neither depend on the $y$ variable. Hence, the strong convexity property of $\bar{\ell}, l_n$ and $l_n+\lambda \|\cdot\|_1$ are the same.

\begin{proof}[Proof of Theorem \ref{thm:regstat}]
The proof follows the outline of Wainwright's proof in \cite{Wbook} (Chapter 7) for subset selection by Lasso, except that our likelihood involves the truncation set, which significantly complicates the analysis.
}

Let:
$$F(\vec{\Omega}) = l_n(\vec{\Omega}) + \lambda \|\vec{\Omega}\|_1.$$
Clearly, $F$ is also convex since $l_n$ is. Now, any optimum $\hat{\vec{\Omega}} \in \arg \min F(\vec{\Omega})$ has to satisfy the zero-subgradient condition:
\begin{equation}\label{eqn:zsub}
\nabla l_n(\hat{\vec{\Omega}}) + \lambda \hat{\vec{W}} = 0
\end{equation}
where $\hat{\vec{W}} \in \partial \|\hat{\vec{\Omega}}\|_1$ and $\nabla l_n$ is as in (\ref{eqn:reggrad}).

Recall that $K \subseteq [d]$ denotes the support of $\vec{\Omega}^\ast$ and $|K| = k$. Let
\begin{equation}\label{eqn:subprob}
\check{\vec{\Omega}} \in \arg \min_{\vec{\Omega} \in \R^{d-1}: \forall j \notin K, \Omega_j = 0} F(\vec{\Omega})
\end{equation}
The rest of the proof goes as follows. First, we establish strong convexity of the restricted likelihood function:
\[
l_n^{K}(\vec{\Omega}) = \frac1n \sum_{i=1}^n \left(\frac{1}{2} {y^{(i)}}^2 -  \vec{x}^{(i)}\vec{\Omega}_{K} y^{(i)} - \ln \int \exp\left(-\frac{1}{2} z^2+ \vec{x}^{(i)}_{K}\vec{\Omega}  z\right) S(z) dz\right),
\]
when $\vec{\Omega}$ lies in a neighborhood of $\vec{\Omega}^*$.
We show that our choice of $\lambda$ implies that $\check{\vec{\Omega}}$ falls in this neighborhood, and hence, there is a unique choice of $\check{\vec{\Omega}}$ in (\ref{eqn:subprob}).
Next, we use the {primal-dual witness method} to show that if strict dual feasibility holds, then $\hat{\vec{\Omega}}$ must in fact equal $\check{\vec{\Omega}}$.
 Then, we verify that strict dual feasibility holds under our choice of parameters and assumptions, establishing parts (a) and (b) of Theorem \ref{thm:regstat}. Finally, it remains to bound the $\ell_\infty$-distance between $\check{\vec{\Omega}}$ and $\vec{\Omega}^*$, proving part (c).

\ignore{
\begin{lemma}\label{lem:subunique}
If $n \geq {\Omega}(m^2 \cdot \mathrm{polylog}(mn/\alpha \delta))$, then with probability at least $1-\delta$, $\check{\vec{\Omega}}$ in (\ref{eqn:subprob}) is uniquely defined.
\end{lemma}
\begin{proof}
Define the restricted likelihood function $l_n^{T}: \R^{|T|} \to \R$:}

\paragraph{Local strong convexity:}
We first show that $l_n^K$ is strongly convex for $\vec{\Omega}$ within a ball centered at $\vec{\Omega}^*$. Below, $\vec{\Omega}^\ast_{K}$ is the restriction of $\vec{\Omega}^\ast$ to the coordinates in $K$.
\begin{lemma}\label{lem:locstrong}
There exists $\kappa\geq \Omega( \alpha^4\cdot \sigma_{\min} )>0$ such that $\nabla^2l_n^{K}(\vec{\Omega}) \succeq \kappa\cdot \vec{I}$ for all $\vec{\Omega}\in \R^{k}$ satisfying $\|\vec{\Omega}-\vec{\Omega}_{K}^*\|_2\leq \frac{1}{C\sqrt{k}}$.
\end{lemma}
\begin{proof}
	Computing the Hessian of $l_n^{K}$:
	\begin{align*}
		\nabla^2 l_n^{K}(\vec{\Omega}) &= \frac1n \sum_{i=1}^n \Cov_{z^{(i)} \sim \mathcal{N}(\vec{x}^{(i)}_K\vec{\Omega},1,S)}[\vec{x}^{(i)}_Kz^{(i)},\vec{x}^{(i)}_Kz^{(i)}]\\
		&= \frac1n \sum_{i=1}^n {\vec{x}_K^{(i)}}^\top {\vec{x}_K^{(i)}} \cdot \E_{z^{(i)} \sim \mathcal{N}(\vec{x}^{(i)}_K\vec{\Omega},1,S)}[(z^{(i)}-\E z^{(i)})^2]\\
		&\succeq  \frac{1}{12n} \sum_{i=1}^n {\vec{x}_K^{(i)}}^\top {\vec{x}_K^{(i)}} \cdot (\alpha(\vec{\Omega},\vec{x}^{(i)}))^2\\
		&\succeq \frac{1}{12e^2n} \sum_{i=1}^n {\vec{x}_K^{(i)}}^\top {\vec{x}_K^{(i)}} (\alpha(\vec{\Omega}^*, \vec{x}^{(i)}))^4 \cdot \exp\left(-2|\vec{x}^{(i)}_K(\vec{\Omega}-{\vec{\Omega}^*_{K}})|^2-4\right)

	\end{align*}
	where the third line\footnote{We abuse notation in the third line. When we say $\alpha(\vec{\Omega},\vec{x}^{(i)})$, we mean by $\vec{\Omega}$ the extension of the vector to $\R^d$ where the coordinates not in $K$ are set to zero.} follows from Lemma \ref{lem:das1} and the fourth line follows from Lemma \ref{lem:das2}. Recall that by Assumption \ref{ass:norm},  $\|\vec{x}_K^{(i)}\|_\infty \leq C$, and hence, $\|\vec{x}_K^{(i)}\|_2 \leq C\sqrt{k}$. Plugging into the above, and again using Assumptions \ref{ass:sur} and \ref{ass:id}, we obtain:
	\[\nabla^2 l_n^{K}(\vec{\Omega}) \succeq \frac{1}{12e^2} \cdot \alpha^4 \cdot e^{-6} \cdot \sigma_{\min}  \vec{I}.\]
\end{proof}

\ignore{
Using Lemma \ref{lem:covest}, since $n \geq \tilde{\Omega}(m\log \alpha^{-1} \log^2 \delta^{-1})$,
$$\frac1n\sum_{i=1}^n \vec{x}_K^{(i)} {\vec{x}_K^{(i)}}^\top \succeq c_2 \E_{\vec{x}_K}[\vec{x}_K \vec{x}_K^\top]$$
with probability at least $1-\delta$, for some $c_2 > 0$.  Here, in the application of Lemma \ref{lem:covest}, we define $F(\vec{x}_K)$ as $S(\vec{x})$ where $\vec{x}=(\vec{x}_K,\vec{x}_{\bar{T}})$ is sampled from $\mathcal{N}(0,{\vec{\Omega}^\ast}^{-1})$. Similarly applying Lemma \ref{lem:covest2}:
$$\E_{\vec{x}_K}[\vec{x}_K \vec{x}_K^\top] \succeq \Omega(\alpha^2)\cdot ({\vec{\Omega}^\ast}^{-1})_{TT}.$$
The lemma follows because by Assumption \ref{ass:id}, the minimum eigenvalue of $({\vec{\Omega}^\ast}^{-1})_{TT}$ is positive}

\paragraph{Bounding the $\ell_2$-distance between $\check{\vec{\Omega}}$ and $\vec{\Omega}^*$:}
Let $r = \frac{1}{C\sqrt{k}}$ be the radius of the ball $B_r$ around $\vec{\Omega}_{K}^*$ inside which $l_n^{K}$ is strongly convex (by Lemma \ref{lem:locstrong}). This means that $l_n^{K}(\vec{\Omega})+\lambda  \|\vec{\Omega}\|_1$ is also locally strongly convex in $B_r$. The next proposition shows that for an appropriate choice of $\lambda $, $\check{\vec{\Omega}}$, defined in (\ref{eqn:subprob}) as the minimizer of $l_n^{K}(\vec{\Omega})+\lambda  \|\vec{\Omega}\|_1$, is in the ball $B_r$.

\begin{lemma}\label{lem:lambda}
If $2\|\nabla l_n^{T}(\vec{\Omega}^*_{K})\|_\infty < \lambda  <\frac{2\kappa r}{3\sqrt{k}}$, where $\kappa$ and $r$ are as above, then $\check{\vec{\Omega}} \in B_r$. Moreover, our choice of $\lambda $ satisfies these conditions with high probability.
\end{lemma}
\begin{proof}
	The first part follows exactly the same steps as the proof of Lemma \ref{lem:mainbig}, and so we omit it. For the second part, note that:
	\[\nabla l_n^{K}(\vec{\Omega}^*_{K}) = -\frac1n \sum_{i=1}^n \left(\vec{x}^{(i)}_K y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\vec{x}_{K}^{(i)}{\vec{\Omega}^*_{K}}, 1, S)}[\vec{x}_{K}^{(i)} z^{(i)}]\right).\]
Consider the $i$'th summand $\vec{x}^{(i)}_K\cdot \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\vec{x}_{K}^{(i)}{\vec{\Omega}^*_{K}}, 1, S)}[z^{(i)}]\right)$. For every $i$, each coordinate of the $i$'th summand has mean zero. Also, for every $i$, each coordinate of the $i$'th summand is bounded by $O(C \sqrt{\log(n/\alpha)})$ with high probability because:
	\begin{itemize}
	\item[(i)] $\|\vec{x}_K^{(i)}\|_\infty \leq C$ for all $i$ by Assumption \ref{ass:norm}.
\item[(ii)]	 $y^{(i)}-\vec{x}_K^{(i)}\vec{\Omega}_K^* $ is distributed as a standard normal truncated to a set of volume at least $\alpha$. The maximum of $n/\alpha$ standard normal variables is $O(\sqrt{\log(n/\alpha)})$ with high probability.
\item[(iii)] $\vec{x}_K^{(i)}\vec{\Omega}_K^*  - \E[\mathcal{N}(\vec{x}_{K}^{(i)}{\vec{\Omega}^*_{K}}, 1, S)]= \E[\mathcal{N}(\vec{x}_{K}^{(i)}{\vec{\Omega}^*_{K}}, 1)] - \E[\mathcal{N}(\vec{x}_{K}^{(i)}{\vec{\Omega}^*_{K}}, 1, S)]$ is bounded by $O(\sqrt{\log(1/\alpha)})$ by Lemma \ref{lem:covest2}.
\end{itemize}

By the Hoeffding bound, $\|\nabla \ell_{K}(\vec{\Omega}^*_{K})\|_\infty < t$ with high probability if $n \geq {\Omega}(C^2\log k\log(n/\alpha)/t^2)$. Plugging in $t = O(\kappa r/\sqrt{k})$ and the values of $\kappa$ and $r$ from Lemma \ref{lem:locstrong}, we see that the constraint is non-vacuous if $n\geq \tilde{\Omega}(C^2/(\kappa^2r^2/k)) = \tilde{\Omega}(C^4k^2/\alpha^8\sigma_{\min} ^2)$. The condition on $n$ is satisfied by the hypotheses of Theorem \ref{thm:regstat}.
\end{proof}

\noindent The above two lemmas imply that $\check{\vec{\Omega}}$ is uniquely defined. Now, the goal is to relate it to the structure of $\hat{\vec{\Omega}}$.
\paragraph{Unique global minimum under strict dual feasibility:}
We construct a vector $\check{\vec{W}}$ so that $(\check{\vec{\Omega}}, \check{\vec{W}})$ satisfy the zero subgradient condition (\ref{eqn:zsub}). Note that by definition, $\check{\vec{\Omega}}$ satisfies the restricted zero-subgradient condition on the coordinates in $K$:
$$\frac1n \sum_{i=1}^n \vec{x}_K^{(i)} y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\vec{x}^{(i)}_K\check{\vec{\Omega}},1,S))}[\vec{x}_{K}^{(i)} z^{(i)}] - \lambda \check{\vec{W}}_{K} = 0$$
for some $\check{\vec{W}}_{K} \in \partial \|\check{\vec{\Omega}}_{K}\|_1$. We set $\check{\vec{W}}$ so that it restricts to $\check{\vec{W}}_{K}$ on $K$ and satisfies the zero-subgradient condition (\ref{eqn:zsub}) on all other coordinates as well.

\begin{lemma}\label{lem:uniquemin}
If $\|\check{\vec{W}}_{-K}\|_\infty < 1$, then $\check{\vec{\Omega}} = \hat{\vec{\Omega}}$ is the unique minimizer of $F$.
\end{lemma}
\begin{proof}
Note that $\langle \check{\vec{W}}, \check{\vec{\Omega}} \rangle = \|\check{\vec{\Omega}}\|_1$ because outside $K$, $\check{\vec{\Omega}}$ is zero, and $\check{\vec{W}}_{K} \in \partial \|\vec{\Omega}_{K}\|_1$. Then, since $F(\hat{\vec{\Omega}}) \leq F(\check{\vec{\Omega}})$:
\begin{align*}
\lambda \|\hat{\vec{\Omega}}\|_1 &\leq l_n(\check{\vec{\Omega}}) + \lambda \|\check{\vec{\Omega}}\|_1 - l_n(\hat{\vec{\Omega}})\\
&= l_n(\check{\vec{\Omega}}) - l_n(\hat{\vec{\Omega}}) + \langle \lambda \check{\vec{W}}, \check{\vec{\Omega}}\rangle \\
&= l_n(\check{\vec{\Omega}}) - l_n(\hat{\vec{\Omega}}) -  \langle \nabla l_n(\check{\vec{\Omega}}), \check{\vec{\Omega}}\rangle
\end{align*}
where we used the fact that $\check{\vec{\Omega}}$ and $\check{\vec{W}}$ satisfy the zero-subgradient condition (\ref{eqn:zsub}). Invoking the convexity of $l_n$:
\begin{align*}
\lambda \|\hat{\vec{\Omega}}\|_1&\leq - \langle \nabla \bar{l_n}(\check{\vec{\Omega}}), \hat{\vec{\Omega}}\rangle = \lambda \langle \check{\vec{W}}, \hat{\vec{\Omega}}\rangle
\end{align*}
Hence, if $|\check{\vec{W}}_{K}| < 1$ for any $s$, then $\hat{\vec{\Omega}}_{K} = 0$. The claim then follows since we have already established that $\check{\vec{\Omega}}$ is defined uniquely.
\end{proof}

\paragraph{Verifying strict dual feasibility:} We next confirm that the $\check{\vec{W}}$ vector constructed above satisfies the condition of Lemma \ref{lem:uniquemin}.
\begin{lemma}
With high probability, $\|\check{\vec{W}}_{-K}\|_\infty<1$.
\end{lemma}
\begin{proof}
Since $(\check{\vec{\Omega}}, \check{\vec{W}})$ satisfy the zero subgradient condition (\ref{eqn:zsub}), we can solve for $\check{\vec{W}}_{-K}$:
\begin{align}
\check{\vec{W}}_{-K}
&=\frac{1}{n\lambda }\sum_{i=1}^n {\vec{x}^{(i)}_{-K}}^\top \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}( \vec{x}^{(i)}\check{\vec{\Omega}}, 1, S)}z^{(i)}\right)\nonumber\\
&=\frac{1}{n\lambda } \sum_i {\vec{x}^{(i)}_{-K}}^\top \left({\vec{x}_{K}^{(i)}} (\vec{\Omega}^* - \check{\vec{\Omega}})+ {z^*}^{(i)} - \E \check{z}^{(i)}\right)\label{eqn:j-K}
\end{align}
where ${z^*}^{(i)} \sim N(0,1, S(\cdot + \vec{\Omega}^* \vec{x}^{(i)}))$ and ${\check{z}}^{(i)}\sim N(0,1, S(\cdot +  \vec{x}^{(i)}\check{\vec{\Omega}}))$. Similarly, we solve for $\check{\vec{W}}_{K}$:
\begin{align*}
\check{\vec{W}}_{K}
&=\frac{1}{n\lambda }\sum_{i=1}^n {\vec{x}^{(i)}_{K}}^\top \left(y^{(i)} - \E_{z^{(i)} \sim \mathcal{N}(\vec{x}^{(i)}\check{\vec{\Omega}}, 1, S)}z^{(i)}\right)\nonumber\\
&=\frac{1}{n\lambda } \sum_i {\vec{x}^{(i)}_{K}}^\top \left({\vec{x}_{K}^{(i)}} (\vec{\Omega}^*-\check{\vec{\Omega}}) + {z^*}^{(i)} - \E \check{z}^{(i)}\right)\label{eqn:j-K}
\end{align*}
Let $\vec{u}$ denote the random vector whose $i$'th coordinate is ${z^*}^{(i)} - \E \check{z}^{(i)}$; note that the components of $\vec{u}$ are independent.  We can rewrite the above as:
\begin{equation}\label{eqn:omegadiff}
\vec{\Omega}^*-\check{\vec{\Omega}}  = \lambda n (\vec{X}_K^T \vec{X}_K)^{-1} \check{\vec{W}}_K - (\vec{X}_{K}^\top \vec{X}_K)^{-1}\vec{X}_K^\top \vec{u}
\end{equation}
Substituting back into (\ref{eqn:j-K}), we get:
\begin{equation}\label{eqn:boundonw}
\vec{W}_{-K} = \vec{X}_{-K}^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K + \frac{1}{\lambda n} \vec{X}_{-K}^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}.
\end{equation}
We analyze the contribution of each of the two terms above separately.
\begin{claim}
$\|\vec{X}_{-K}^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K\|_\infty \leq \beta$.
\end{claim}
\begin{proof}
For any $j \notin K$,
\[|\vec{x}_j^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1} \check{\vec{W}}_K| \leq \|\vec{x}_j^\top \vec{X}_K (\vec{X}_K^\top \vec{X}_K)^{-1}\|_1 \leq \beta\]
by Assumption \ref{ass:inc}.
\end{proof}
\begin{claim}\label{clm:randdual}
With high probability, $\|\frac{1}{\lambda n} \vec{X}_{-K}^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}\|_\infty \leq \frac{1-\beta}{2}.$
\end{claim}
\begin{proof}
For any $j \notin K$, let $\vec{v}_j^\top = \vec{x}_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top)$. Note that $\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top$ is an
orthogonal projection matrix, and hence, by Assumption \ref{ass:norm}, $\|\vec{v}_j\|_2 \leq \|\vec{x}_j\|_2 \leq C\sqrt{n}$ and $\|\vec{v}_j\|_1 \leq Cn$.

Write $\vec{u} = \vec{z}^* - \E[\check{\vec{z}}]$. By the triangle inequality, it suffices to bound: (i) $\frac{1}{\lambda n} |\vec{v}_j^\top (\vec{z}^* - \E[\vec{z}^*])|$ and (ii) $\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])|$.

We first bound (ii).
\[
\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])| \leq \frac{1}{\lambda n} \|\vec{v}_j\|_1 \|\E[\vec{z}^*] - \E[\check{\vec{z}}])\|_\infty \leq \frac{C}{\lambda } \cdot\max_{i \in [n]} (|\E[{z^*}^{(i)}]| + |\E[\check{z}^{(i)}]|)
\]
Since each ${z^*}^{(i)}$ is a standard normal truncated to a set of volume at least $\alpha$, Lemma \ref{lem:covest2} implies $\E[{z^*}^{(i)}] = O(\sqrt{\log(1/\alpha)})$.  Similarly, $\E[\check{z}^{(i)}] = O\left(\sqrt{\log(1/\alpha(\check{\vec{\Omega}}_K, \vec{x}_K^{(i)}))}\right)$. Invoking the fact that $\|\vec{\Omega}^* - \check{\vec{\Omega}}\|_2 \leq \frac{1}{C\sqrt{k}}$ and Lemma \ref{lem:das2}, we obtain that $\alpha(\check{\vec{\Omega}}, \vec{x}^{(i)}) = \Omega(\alpha^2)$. Hence, we get:
\[
\frac{1}{\lambda n} |\vec{v}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])|\leq \frac{C}{\lambda } \cdot O(\sqrt{\log(1/\alpha)}) \leq O\left(\frac{C^2k}{\alpha^5 \sigma_{\min} }\right) < \frac{1-\beta}{4}.
\]
where we used the assumption in the Theorem.

Now, we turn to (i). Observe that $\vec{\zeta}^* = \vec{z}^* - \E[\vec{z}^*]$ is a zero-mean vector with independent components ${\zeta^*}^{(1)}, \dots, {\zeta^*}^{(n)}$. In order to bound $\vec{v}_j^\top \vec{\zeta}^* = \sum_{i \in [n]} {v}_j^{(i)} {\zeta^*}^{(i)}$, we use Bernstein's inequality. Fix an $i \in [n]$, and let $\zeta$ denote ${\zeta^*}^{(i)}$. For Bernstein's Lemma, we need bounds on $\E[{{\zeta}}^p]$ for $p>1$. It is easy to see that these quantities are maximized when $\zeta \sim \mathcal{N}(0,1,S_q)$ where $S_q = \{x : x^2 \geq q\}$ for some $q$ chosen such that $\mathcal{N}(0,1,S_q)=\alpha$. Routine calculations (Lemma 13 of \cite{Das19})  show that $\E[\zeta^2] \leq 2 + 2 \log(2/\alpha)$ and $\E[\zeta^p] \leq p! (2+2\log(2/\alpha))^p$. Applying Bernstein, we get that with probability $1-\exp(-t^2)$,  $\frac{1}{\lambda n} |\vec{v}_j^T \vec{\zeta}^*| \leq O\left(\frac{Ct\log(1/\alpha)}{\lambda \sqrt{n}}\right)$ for $t \leq O(\sqrt{n/\log(1/\alpha)})$.  Setting $t = \Omega(\sqrt{\log d})$, we get that with high probability, for all $j \notin K$:
\[
\frac{1}{\lambda n} |\vec{v}_j^T \vec{\zeta}^*| \leq O\left(\frac{C\sqrt{\log d}\log(1/\alpha)}{\lambda \sqrt{n}}\right) = O\left(\frac{C^2 k \sqrt{\log d}\log(1/\alpha)}{\alpha^4 \sigma_{\min}  \sqrt{n}}\right).
\]
If we take $n \geq \Omega((C^4k^2\log d)/((1-\beta)^2\sigma_{\min} ^2 \alpha^9))$, then the above is less than $(1-\beta)/4$. This proves the claim.
\end{proof}

\paragraph{Bounding the $\ell_\infty$-error:} The max-error can be bounded using (\ref{eqn:omegadiff}).
\[
\|\check{\vec{\Omega}}-\vec{\Omega}^*\|_\infty \leq \lambda  \opnorm*{\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}}_\infty + \left\|\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\vec{X}_K^\top \frac{\vec{u}}{n}\right\|_\infty
\]
where for a matrix $A$ with $r$ rows, $\opnorm{A}_\infty = \max_{i \in [r]} \|A^{(i)}\|_1$ is the matrix $\ell_\infty$-norm.

The first term is deterministic and can be bounded as follows:
\[
\lambda  \opnorm*{\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}}_\infty \leq \lambda  \sqrt{k}\cdot \lambda_{\max}\left(\left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\right) \leq \frac{\lambda  \sqrt{k}}{\sigma_{\min} } = O\left(\frac{\alpha^4}{C\sqrt{k}}\right)
\]

To analyze the second term, define for $j \in K$, the vector $\vec{w}_j^\top = \vec{e}_j^\top \left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\frac{\vec{X}_K^\top}{n}$. We need to bound $\max_{j\in K} |\vec{w}_j^\top \vec{u}|$.
Note that $\|\vec{w}_j\|_2^2 = 	\frac1n \vec{e}_j^\top \left(\frac{\vec{X}_K^\top \vec{X}_K}{n}\right)^{-1}\vec{e}_j \leq \frac{1}{n \sigma_{\min} }$.
Similar to the analysis in the proof of Claim \ref{clm:randdual}, we write $\vec{u}$ as $(\vec{z}^* - \E[\vec{z}^*]) + (\E[\vec{z}^*] - \E[\check{\vec{z}}])$. The quantity $\max_{j \in K}|\vec{w}_j^\top (\vec{z}^* - \E[\vec{z}^*])|$ can be
shown using Bernstein's inequality to be at most $O\left(\frac{\sqrt{\log k}\log(1/\alpha)}{\sqrt{\sigma_{\min}  n}}\right)$ with high probability. The other term can be bounded as:
\[
\max_{j \in K} |\vec{w}_j^\top (\E[\vec{z}^*] - \E[\check{\vec{z}}])| \leq \max_{j \in K} \|\vec{w}_j\|_1 O(\sqrt{\log(1/\alpha)}) \leq O\left(\sqrt{\frac{\log(1/\alpha)}{\sigma_{\min} }}\right)
\]
So, putting everything together:
\[
\|\check{\vec{\Omega}}-\vec{\Omega}^*\|_\infty \leq O\left(\sqrt{\frac{\log(1/\alpha)}{\sigma_{\min} }} + \frac{\alpha^4}{C\sqrt{k}} + \frac{\sqrt{\log k}\log(1/\alpha)}{\sqrt{\sigma_{\min}  n}} \right).
\]
The last term is negligible because of the lower bound on $n$.
\ignore{
 The $j$'th component of the second term in (\ref{eqn:boundonw}) is bounded as:
\[
\frac{1}{\lambda n} |{X}_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top) \vec{u}|
\leq \frac{1}{\lambda n} \|X_j^\top (\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top)\|_2  \cdot \|u\|_2 \leq \frac{\|X_j\|_2}{\lambda n} \cdot \|u\|_2.
\]
where we used the fact that $\vec{I}-\vec{X}_K(\vec{X}_K^\top \vec{X}_K)^{-1} \vec{X}_K^\top$ is an orthogonal projection matrix. By Assumption \ref{ass:id}, $\|X_j\|_2 \leq K\sqrt{n}$. It remains to bound $\|u\|_2$.

The first term is bounded by $1-\beta$ by Assumption \ref{ass:inc}. For the second term, note that $\|u\|=O(1)$ because they correspond to truncations according to sets that are close as we have already shown that $\|\check{\vec{\Omega}}-\vec{\Omega}^*\|\leq r$. Our desired bound follows by choice of $\lambda$.}
\end{proof}

config: arxiv


TITLE: Removing removable discontinuities in Riemann integration
QUESTION [0 upvotes]: Suppose $f:[a,b]\rightarrow\mathbb{R}$ is Riemann integrable on $[a,b]$, has a finite number of removable discontinuities, and  $\lim\limits_{t\rightarrow x} f(t)$ exists for all $x$. Let $g(x) = \lim\limits_{t\rightarrow x} f(t)$. I'm wondering if the following is always true for $h$ Riemann integrable:
$$\int_a^b f(x)h(x) dx = \int_a^b g(x)h(x)dx$$
I guess you could just say that $f\cdot h$ is also Riemann integrable, and then $g\cdot h$ is the result of removing discontinuities from $f$. Is this sound reasoning?

REPLY [3 votes]: Answering your last comment...It is a well-known theorem that a bounded function on a finite interval $[a,b]$ is Riemann integrable if and only if the set of discontinuities of $f$ is a set of measure zero; of course, if $f$ has a finite number of discontinuities, then this set certainly has measure zero and so $f$ is Riemann integrable.  It is another well-known fact that Riemann integrable functions which differ on sets of measure zero have equal integrals.  The way you have defined $g$ makes it Riemann integrable (since $g$ is continuous), and by assumption $h$ is Riemann integrable on $[a,b]$.  Hence, $gh$ and $fh$ are both Riemann integrable (another well-known fact), so both integrals exist, and since $fh=gh$ almost everywhere (you can define $fh$ however you please at the points of discontinuity), their integrals are equal (you can look up any of these 'well-known' facts by a simple Google search or reference text on basic analysis; some of the special cases, e.g. reducing measure zero sets to finite sets are easier and straight-forward to prove with standard partition/epsilon regularization arguments).
Your reasoning isn't very well refined either.  I think you're missing the essential point that integration (Riemann, Lebesgue, or otherwise) "doesn't care" about how a function is defined on sets of measure zero; it could be $+\infty$, $0$, $\pi$, $e$, $2.399$, whatever at such points and the integral will "ignore" these modifications.  That heuristic is helpful to keep in mind in integration theory.  Another one is that integration is a smoothing process that accepts much rougher functions and outputs even smoother (or just as smooth) of functions, as where differentiation is a "roughing-up" process that accepts only smooth functions and outputs (in general) rougher functions (or at the very least, just as smooth).  Part of this ladder heuristic is encoded in the fundamental theorem of calculus (both parts) which is often overlooked by first-learners.


text:
\begin{document}

\title{Plane drawings of the generalized Delaunay-graphs for pseudo-disks\thanks{Research by the first author was supported by the National Research, Development and Innovation Office -- NKFIH under the grant K 116769. Research by both authors was supported by the Lend\"ulet program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017.}}

\author{Bal\'azs Keszegh\inst{1,2} \and
	D\"om\"ot\"or P\'alv\"olgyi\inst{2}}

\authorrunning{B. Keszegh and D. P\'alv\"olgyi}

\institute{Alfr\'ed R{\'e}nyi Institute of Mathematics, Hungarian Academy of Sciences Re\'altanoda u. 13-15 Budapest, 1053 Hungary. E-mail: \email{keszegh@renyi.hu}
	\and
	MTA-ELTE Lend\"ulet Combinatorial Geometry Research Group, Institute of Mathematics, E\"otv\"os Lor\'and University (ELTE), Budapest, Hungary.}

\maketitle

\begin{abstract}
	We study general Delaunay-graphs, which are a natural generalizations of Delaunay triangulations to arbitrary families.
We prove that for any finite pseudo-disk family and point set, there is a plane drawing of their Delaunay-graph such that every edge lies inside every pseudo-disk that contains its endpoints.

\keywords{Delaunay-graph \and pseudo-disk \and topological hypergraphs}
\end{abstract}

\section{Introduction}\setcounter{footnote}{0}

Delaunay triangulations play a central role in discrete and computational geometry. In many applications, however, one needs to deal with a different topology which requires to substitute disks in the definition with another family. If this other family consists of the homothets\footnote{The homothetic copy of a set is its scaled and translated copy (roations are not allowed).} of some convex shape, then most properties generalize in a straight-forward manner \cite{Ma2000}. In this paper we study what happens when this is not the case, i.e., we only suppose that our underlying family is a family of (possibly non-convex) pseudo-disks. Now we make the exact definitions.

\begin{defi}
Given a finite set of points $S$ and a family of regions $\F$, the vertices of the \emph{Delaunay-graph $\D({S,\F})$ of $S$ with respect to $\F$} correspond to the points of $S$, and two vertices $p,q\in S$ are connected by an edge if there is an $F\in \F$ such that $S\cap F=\{p,q\}$.
\end{defi}

Note that if $S\subset \mathbb R^2$ and $\F$ is the family of disks, this gives back the usual definition of Delaunay triangulations.
It is well-known that this graph with respect to disks is planar, moreover, drawing its edges as straight-line segments we get a plane drawing in which the drawing of an edge $pq$ lies inside every disk containing both $p$ and $q$.
This is true also when the regions are the homothets of some convex region, or more generally, when $\F$ is a pseudo-disk arrangement containing only convex regions (as we will soon see).

\begin{defi}
	A Jordan region is a (simply connected) closed bounded region whose
	boundary is a closed simple Jordan curve.
	A family of Jordan regions is called a \emph{family of pseudo-disks} if the boundaries of every	pair of the regions intersects in at most two points.
\end{defi}

For points with respect to pseudo-disks if we draw the edges in an arbitrary way inside one of their defining pseudo-disks (that is, the edge connecting points $p$ and $q$ is drawn inside an $F\in \F$ for which $H_F=\{p,q\}$), we get a drawing in which non-adjacent edges intersect an even number of times, using the following simple lemma:

\begin{lem}\cite{buzaglo}\label{lem:disjointedges}
	Let $D_1$ and $D_2$ be two pseudo-disks in the plane. Let $x$ and $y$ be two
	points in $D_1\setminus D_2$. Let $a$ and $b$ be two points in $D_2\setminus D_1$. Let $e$ be any Jordan
	arc connecting $x$ and $y$ that is fully contained in $D_1$. Let $f$ be any Jordan arc connecting $a$ and $b$
	that is fully contained in $D_2$. Then $e$ and $f$ cross an even number of times.
\end{lem}

The Hanani-Tutte theorem then implies that the Delaunay-graph of points with respect to pseudo-disks is planar.

If we additionally assume that the pseudo-disks in the family are all convex, then just like in the case of disks and homothets of a convex region, we can draw the edges as straight-line segments. As the regions are convex, the drawing of an edge $pq$ indeed lies inside every pseudo-disk containing both $p$ and $q$. Furthermore, two adjacent edges do not intersect while non-adjacent edges intersect at most once and by Lemma \ref{lem:disjointedges} an even number of times, thus they also do not intersect. Thus,  this is a plane drawing of the Delaunay-graph.

The aim of this paper is to prove that with additional effort we can also get such a plane drawing even when the pseudo-disks are not necessarily convex:

\begin{thm}\label{thm:planedelgraph}
	Given a finite pseudo-disk family $\F$ and a finite point set $S$, there is a plane drawing of the Delaunay-graph of $S$ with respect to $\F$ such that every edge $pq$ lies inside every pseudo-disk containing both $p$ and $q$.
\end{thm}

Note that self-intersecting edges can be always easily replaced by non-self-intersecting ones by removing loops, so in the rest of the paper we suppose that edges have no self-intersection, i.e., they are simple Jordan-curves.

One important consequence of Theorem \ref{thm:planedelgraph} is for pseudo-disk families that are shrinkable.
To state it, first we need the following (restated) lemma from \cite{Pin14}.

\begin{lem}[Pinchasi \cite{Pin14}]\label{lem:shrink2}
	If a pseudo-disk $F\in \F$ contains exactly $k$ points of $S$, one of which is $p\in S$, then for every $2\le l\le k$ there exists a set $F'\subset F$ such that $p\in F'$ and $|F'\cap S|=l$, and $\F\cup\{F'\}$ is again a family of pseudo-disks.
\end{lem}

We say that a pseudo-disk family $\F$ is {\em shrinkable} over $S$ if for every $F\in \F$ the conclusion of Lemma \ref{lem:shrink2} holds for some $F'\in \F$.

An example of a shrinkable pseudo-disk family is the collection of all disks in the plane over a finite $S$ that does not contain four points on a circle.
More generally, instead of disks, we can take the family of all homothets of any convex set with a smooth boundary over a finite $S$ that does not contain four points on the boundary of a homothet.

\begin{cor}
	Given a shrinkable pseudo-disk family $\F$ over a finite point set $S$, for every $F\in\F$ the subgraph of $\D(S,\F)$ (the  Delaunay-graph of $S$ with respect to $\F$) induced by $F\cap S$ is a connected graph.
\end{cor}
\begin{proof}
	Using \ref{lem:shrink2}, there is a point $p\in F\cap S$ such that there is an $F'\in \F$ for which $F'\cap S=F\cap S\setminus \{p\}$.
	By induction, the Delaunay-graph restricted to $F'\cap S$ is connected.
	The same holds for some other point $p'\in F\cap S$.
	Since $F\cap S\setminus \{p\}$ and $F\cap S\setminus \{p'\}$ both induce connected graphs, so does $F\cap S$ unless $F\cap S=\{p,p'\}$, but in this latter case $(p,p')$ is an edge of the Delaunay-graph because of $F$.
	This finishes the proof.
\end{proof}

We expect that such a strong variant of planarity of the Delaunay-graph can be useful in several applications. As an example, in a new result of Ackerman and the authors about certain colorings of the edges of the Delaunay-graph \cite{tuple} Theorem \ref{thm:planedelgraph} was needed.

\section{Proof of Theorem \ref{thm:planedelgraph}}

We will need the following lemma:

\begin{lem}\label{lem:ray}
	Given a finite family of pseudo-disks such that all pseudo-disks contain a common point $p$, any point $q$ can be connected by a Jordan curve to $p$ such that this curve does not intersect the boundary of pseudo-disks containing $q$ (and $p$) and intersects once the boundary of pseudo-disks that do not contain $q$ (but contain $p$).
\end{lem}

In \cite{lenses} it is proved that for a finite family of pseudo-disks all containing a common point $p$ (and the regions are in general position, that is, no three of their boundaries intersecting in a common point), there exists a combinatorially equivalent family of pseudo-disks, all of which are star-shaped with respect to $p$\footnote{A region is star-shaped with respect to $p$ if for every line through $p$ intersects the region in a segment containing $p$.}. Clearly this also implies the above lemma, the only issue is that we do not want to assume that the regions are in general position. Alternately, appropriate application of the Sweeping theorem of Snoeyink and Hershberger \cite{SH89} also implies Lemma \ref{lem:ray} without assuming general position, yet the proof of their theorem is quite involved. Finally, in the manuscript \cite{anchored} a relatively simple self-contained proof of Lemma \ref{lem:ray} is shown, again without assuming general position.

We need some further definitions and lemmas before we can can prove our main result.  From now on every point set $S$ we consider is finite, even if we do not always emphasize this.

\begin{defi}
	Given two pseudo-disks whose boundaries intersect, removing their boundaries the plane is split into three bounded and one unbounded region. We call the bounded regions the \emph{lens} defined by these two pseudo-disks. If a set of points $S$ is given, we say that \emph{a lens is empty} if it does not contain any point from $S$.
\end{defi}

\begin{defi}
	In a pseudo-disk family $\F$, replacing a pseudo-disk $F$ with some $F'\subsetneq F$ such that the new family is still a pseudo-disk family, is called a \emph{shrinking} of $F$ to $F'$. If such an $F'$ already exists in $\F\setminus \{F\}$, then simply deleting $F$ from $\F$ is also called a shrinking of $F$ to $F'$. Given a point set $S$, such a shrinking is \emph{hypergraph preserving} on $S$ if $F'\cap S=F\cap S$.

	Applying shrinking steps to multiple members of the family $\F$ after each other is called a \emph{shrinking} of $\F$.
	A shrinking of $\F$ is \emph{hypergraph preserving} if all shrinking steps are hypergraph preserving.
\end{defi}

\begin{obs}
	If we do a hypergraph preserving shrinking on $\F$ to get $\F'$, then by definition in each step for the shrunk $F\in \F$ we have $H_F=H_{F'}$ and thus the geometric hypergraph of $S$ with respect to $\F$ is the same as of $S$ with respect to $\F'$. That is, a hypergraph preserving shrinking does indeed preserve the geometric hypergraph of $S$ with respect to $\F$.
\end{obs}

\begin{lem}\label{lem:emptylens}
	Given a point set $S$ and a finite family $\F$ of pseudo-disks, if we take a containment-minimal empty lens $L$, and $L$ is defined by the pseudo-disks $F_1$ and $F_2$ such that $L\subset F_1$, then we can get rid of this lens in the following way: we shrink $F_1$ to some $F_1'$ such that $F_1'\cap L=\emptyset$ while $F_1'\cap S=F_1\cap S$ (that is, shrinking $F_1$ to $F_1'$ is hypergraph preserving). Moreover, the number of intersections of the boundaries of pseudo-disks strictly decreases during this.
\end{lem}

\begin{proof}
	Let $l_1$ (resp.\ $l_2$) be the maximal curve which is on the boundary of both $F_1$ (resp.\ $F_2$) and $L$.
	We claim that every maximal curve inside $L$ which is part of a boundary of some pseudo-disk different from $F_1$ and $F_2$, has one endpoint on $l_1$ and another on $l_2$. Indeed, if such a maximal curve on the boundary of some $F_3$ would have both endpoints on $l_1$ (resp.\ $l_2$), then $F_1$ (resp.\ $F_2$) and $F_3$ would define a lens which lies inside $L$ contradicting its containment minimality.

\begin{figure}
	\centering
	\includegraphics[height=4cm]{lensremoval.pdf}
	\caption{Removing the lens $L$ from $F_1$.}
	\label{fig:lensremoval}
\end{figure}

	Now we are ready to shrink $F_1$. Basically we want to delete $L$ from it, but we have to shrink it a bit more to avoid the introduction of common boundary parts which turns out to be a bit technical;\footnote{Deleting from $F_1$ an $\epsilon$-expansion of $L$ would not always work - we leave it to the interested reader why.} see Figure \ref{fig:lensremoval}.  In order to do that we will define a curve inside $F_1\setminus L$ which intersects the boundary of some pseudo-disk the same number of times as $l_2$ does. Then, we shrink $F_1\setminus L$ by essentially replacing $l_2$ by this curve on the boundary. Next we give the details of how we do all of this.

	Consider the arrangement determined by the boundaries of the pseudo-disks. The \emph{vertices} of the \emph{arrangement} are the intersection points of the boundaries of regions, the \emph{edges} are the maximal connected parts of the boundaries of regions that do not contain a vertex and
	the \emph{cells} are the maximal connected parts of the plane which are disjoint from the edges and the vertices of the arrangement.

	Consider the vertices (that is, intersection points) of the arrangement that are on $l_2$ and then for every such vertex and every edge incident to this vertex and lying inside $F_1\setminus L$, but not on $l_2$, we take a small part of that edge ending in this vertex and call this a half-edge. These half-edges can be ordered naturally first according to the order of their endpoints on $l_2$, second for two half-edges sharing an endpoint we order them according to their rotation order around this vertex. The same ordering defines uniquely for every consecutive such half-edges the cell of the arrangement `between' them.

	Thus we get a natural ordering of the half-edges, $e_1,e_2,\dots e_l$. Notice that the first and last half-edge lies on the boundary of $F_1\setminus L$. Now for every $e_i$ choose an arbitrary point $c_i$ on it and connect for every $1\le i\le i-1$ the points $c_i$ and $c_{i+1}$ by a curve lying inside the cell that lies between them. While we need to draw several curves inside one cell (see Figure \ref{fig:lensremoval}), we can draw these curves such that no two of them intersects, as we can draw the curve connecting $c_i$ and $c_{i+1}$ close to their half-edges and (if they do not share an endpoint) the part of $l_2$ separating their endpoints.
	The union of all the curves is a curve $l_1'$ that connects $c_1$ to $c_l$.

	Let $F_1'$ be the region whose boundary consists of this curve and the boundary part of $F_1\setminus l$ from $c_1$ to $c_l$ which is disjoint from $l_2$.

	Having defined $F_1'$, the shrinking of $F_1$, we are left to prove that it has the properties we required.

	Clearly, $F_1'\cap L=\emptyset$ and also $F_1'\cap S=F_1\cap S$. So we need to show only that the new family is also a pseudo-disk family and has strictly less intersections between the boundaries of its members.

	Consider now an intersection of $l_1$ with the boundary of some $F_3$. By definition, it must be $c_i$ for some $2\le i\le i-1$. The half-edge $\gamma_i$ containing $c_i$ has an endpoint on $l_2$, which is an intersection point of the boundaries of $F_3$ and $F_2$. Using our observation from the beginning of the proof, the maximal curve inside $L$ whose starting point is this intersection ends on $l_1$, which was an intersection of the boundary of $F_1$ with the boundary of $F_3$. Arguing now in the opposite direction, for every intersection point of $l_1$ with a boundary of some $F_3$ there is a corresponding intersection point on $l_2$ and then also on $l_1'$ with the boundary of $F_3$. We conclude that the intersection points on the boundary of $F_1$ and $F_1'$ are in bijection except for the two intersection points of the boundaries of $F_1$ and $F_2$ as the boundaries of $F_1'$ and $F_2$ do not intersect. This implies that the family is still a pseudo-disk family and that the overall number of intersection points of boundaries decreased by $2$, finishing the proof.
\end{proof}

\begin{defi}
	Given a point set $S$, we say that a pseudo-disk family  $\F$ \emph{respects} $S$ if for every pair of pseudo-disks $F_1,F_2\in \F$,
	\begin{equation} \label{eq:respect1}
	\text{if } {F_1\cap S}\subseteq {F_2\cap S,} \text{ then } F_1\subseteq F_2 \text{ as well and}
	\end{equation}

	\begin{equation} \label{eq:respect2}
	\text{if } {(F_1\cap S)\cap (F_2\cap S)}=\emptyset,
	\text{ then } F_1\cap F_2=\emptyset \text{ as well.}
	\end{equation}

\end{defi}

\begin{obs}\label{obs:respectunique}
	If a pseudo-disk family $\F$ respects $S$, then by definition for every subset $S'\subseteq S$ there is at most one pseudo-disk $F$ such that $F\cap S=S'$.
\end{obs}

Indeed, if $F_1\cap S=F_2\cap S$, then by assumption (\ref{eq:respect1}) both $F_1\subseteq F_2$ and $F_2\subseteq F_1$, that is $F_1=F_2$.
\begin{lem}\label{lem:respect}
	Given a point set $S$ and a finite pseudo-disk family $\F$, we can shrink $\F$ to get a pseudo-disk family $\F'$ such that
	\begin{itemize}
		\item [(i)]
			this shrinking is hypergraph preserving on $S$ and
		\item [(ii)]
			$\F'$ respects $S$.
	\end{itemize}

\end{lem}

\begin{proof}
We keep applying Lemma \ref{lem:emptylens} to a containment-minimal empty lens until there are no more empty lenses. This is a finite process as in each step the number of intersections between boundaries of pseudo-disks decreases. By Lemma \ref{lem:emptylens} it follows that the new family is a pseudo-disk family and that this shrinking was hypergraph preserving on $S$.

Next, if there is a pair of pseudo-disks which intersect $S$ in the same subset $S'$, then since there are no empty lenses, one of these must be contained in the other.
The bigger one can be shrunk to the smaller, so we can delete it.

We keep doing this until for every $S'$ there is only at most one pseudo-disk which intersects $S$ in $S'$.

Finally, it is easy to see that if there was a pair of pseudo-disks in $\F'$ for which (\ref{eq:respect1}) or (\ref{eq:respect2}) did not hold, then either they would intersect $S$ in the same subset or one of the lenses they form would be empty, contradicting the fact that there were no more empty lenses in $\F'$.
\end{proof}

\begin{defi}
	Given a pseudo-disk family $\F$, the \emph{depth of a point} is the number of pseudo-disks containing this point.
\end{defi}

\begin{lem}\label{lem:transversaledge}
	We are given a point set $S$ and a family of pseudo-disks $\F$ which respects $S$ such that every pseudo-disk contains exactly two points from $S$. Given a pseudo-disk $F_{x,y}\in \F$ containing only the two points $x,y\in S$ from $S$, we can draw a curve connecting $x$ and $y$ which lies completely inside $F_{x,y}$ and intersects the boundary of every other pseudo-disk at most once.
\end{lem}
\begin{proof}
	For any pair $p,q$ of points of $S$, denote by $F_{p,q}$ the unique pseudo-disk containing exactly these two points from $S$, if it exists (uniqueness follows from Observation \ref{obs:respectunique} as $\F$ respects $S$).

		We will draw the curve connecting $x$ and $y$ inside $F_{x,y}$.
	Thus, it cannot intersect any pseudo-disk which lies outside $F_{x,y}$, that is, as $\F$ respects $S$, any pseudo-disk that contains two points of $S$, both different from $x$ and $y$. Thus when drawing the arc, we only need to care about pseudo-disks of two \emph{types}, of type $F_{x,*}$, which is an $F_{x,p}$ for some $p$ different from $y$ and of type $F_{y,*}$, which is an $F_{y,q}$ for some $q$ different from $x$. Note that $F_{x,y}$ has no type.

	If $p\ne q$, then $F_{x,p}\cap F_{y,q}=\emptyset$ as $\F$ respects $S$. This implies the following:

	\begin{prop}\label{prop:thmprop}
	Inside $F_{x,y}$ if a point (not from $S$!) is contained in at least $3$ pseudo-disks besides $F_{x,y}$ (that is, has depth at least $4$), then all these pseudo-disks must be of the same type.
	\end{prop}

\begin{figure}
	\centering
	\includegraphics[height=7cm]{transversal_case12.pdf}
	\caption{Drawing the curve connecting $x$ and $y$.}
	\label{fig:case12}
\end{figure}

	Now we can continue with the proof of Lemma \ref{lem:transversaledge} --- for illustrations see Figure \ref{fig:case12}.

	\begin{itemize}
		\item Case 1. There is a point $z$ (not from $S$) in $F_{x,y}$ contained in pseudo-disks of both types.

	Then by Proposition \ref{prop:thmprop} it must be a $3$-deep point which besides $F_{x,y}$ is contained only in $F_{x,p}$ and $F_{y,p}$ for some $p$. Also, in the arrangement of the pseudo-disks the cell containing $p$ must be bounded only by boundary parts of the three regions otherwise a point in a neighboring cell would contradict Proposition \ref{prop:thmprop}. In fact, it is easy to see that it must be bounded by parts of the boundaries of all of these three regions, otherwise we would have an empty lense.

	Take now the arrangement defined by $F_{x,y}$ and the regions of type $F_{x,*}$. Let $C_x$ be the cell containing $z$ in this arrangement. Take the first intersection point $z_x$ of the ray guaranteed by Lemma \ref{lem:ray} going from $z$ to $x$ with the boundary of $C_x$. Note that $C_x$ is disjoint from all pseudo-disks of type $F_{y,*}$ except for $F_{y,p}$. Moreover, again by Proposition \ref{prop:thmprop}, the boundary of $F_{y,p}$ intersects the boundary of $F_{x,y}$ and the boundary of $F_{x,p}$ in two points but does not intersect the boundaries of other pseudo-disks of type $F_{x,p}$. Thus, $F_{y,*}$ subdivides $C_x$ into at most three parts, to $C'$, containing $p$, to $C_x'$, having $z_x$ on its boundary, and to a possible third cell. It is easy to see that $C'$ and $C_x'$ must share boundary parts, and so we can choose a point $z_x'$ on their common boundary. Note that $C'$ is actually the cell containing $z$ in the arrangement of all pseudo-disks.

	Now take the arrangement defined by $F_{x,y}$ and the regions of type $F_{y,*}$. A symmetric argument gives the cells $C'$ and $C_y'$ and the points $z_y$ and $z_y'$ (note that we get the same $C'$ as it is again the cell containing $z$ in the arrangement of all pseudo-disks).

	Now the curve connecting $x$ and $y$, and intersecting the boundary of every pseudo-disk at most once consists of the following
	parts: a curve from $x$ to $z_x$ along a ray guaranteed by Lemma \ref{lem:ray} (applied for the pseudo-disks containing $x$), a curve inside $C_x'$ from $z_x$ to $z_x'$, a curve from $z_x'$ to $z_y'$ inside $C'$ (which can go through $z$ if we wish to), a curve from $z_y'$ to $z_y$ inside $C_y'$ and finally a curve from $z_y$ to $y$ along a ray guaranteed by Lemma \ref{lem:ray} (applied for the pseudo-disks containing $y$). By Lemma \ref{lem:ray} every point of the curve connecting $x$ and $z_x$ is inside at least two pseudo-disks of type $F_{x,*}$ and thus by Proposition \ref{prop:thmprop} it cannot intersect any pseudo-disks of type $F_{y,*}$. Similarly, the curve connecting $y$ and $z_y$ cannot intersect any pseudo-disks of type $F_{x,*}$.
	Altogether, using again Lemma \ref{lem:ray}, we get that the union of these curves defines a curve intersecting every pseudo-disk boundary at most once, as required.

\item	Case 2. Every point in $F_{x,y}$ is contained only in pseudo-disks of one type.

	In this case going along an arbitrary curve $\gamma$ from $x$ to $y$, the last point $z_x$ which is contained in a pseudo-disk of type $F_{x,*}$ must be at least $2$-deep and contained in $F_{x,y}$ and in pseudo-disks only of type $F_{x,*}$ (if there are no pseudo-disks of type $F_{x,*}$, let $z_x=x$.). Going further along this curve towards $y$, there are $1$-deep points and then the first at least $2$-deep point $z_y$ must be contained in $F_{x,y}$ and in pseudo-disks only of type $F_{y,*}$ (or if there are none, let $z_y=y$.). Now we can apply Lemma \ref{lem:ray} to get a curve from $x$ to $z_x$  (applied for the pseudo-disks containing $x$). This will be disjoint from each $F_{y,*}$, as there no points in $F_{x,y}$ contained in pseudo-disks of both types. We similarly connect $y$ to $z_y$. Together with the part of $\gamma$ connecting $z_x$ to $z_y$ we get again a curve, which using again Lemma \ref{lem:ray} is intersecting every pseudo-disk boundary at most once, as required.
	\end{itemize}
	\end{proof}

\begin{proof}[of Theorem \ref{thm:planedelgraph}]
	Given a finite pseudo-disk family $\F$ and a point set $S$, we want to find a plane drawing of the Delaunay-graph of $S$ with respect to $\F$ such that every edge $pq$ lies inside every pseudo-disk containing both $p$ and $q$.

	First we shrink $\F$ using Lemma \ref{lem:respect} to get a family which respects $S$. As we did a hypergraph preserving shrinking on $S$, the new family has the same (possibly empty!) Delaunay-graph as $\F$. Next we remove all the pseudo-disks containing at least $3$ points from $S$, by which the Delaunay-graph is again left intact. We get the pseudo-disk family $\F'$. Notice that as $\F'$ respects $S$, for every pair of points $p,q$ which are connected by an edge in the Delaunay-graph, in $\F'$ there is exactly one pseudo-disk $F'_{pq}$ which contains these two points (and no other point of $S$).

	We claim that a plane drawing of the Delaunay-graph of $\F'$ with respect to $S$ such that for each edge $pq$ its drawing lies inside $F'_{pq}$ is as required for $\F$ with respect to $S$. Indeed, take an arbitrary edge $pq$ of the Delaunay-graph of $\F$ with respect to $S$ and let $F$ be an arbitrary pseudo-disk such that $p,q\in F\in \F$. After shrinking $\F$ to $\F'$, $F$ was shrunk to some $F'$ (possibly in multiple steps) which must contain $F'_{pq}$ as $F'\cap S=F\cap S\supset \{p,q\}=F'_{pq}\cap S$ and $\F'$ respects $S$. Thus, the drawing of the edge $pq$ lies inside $F'_{pq}\subset F'\subset F$, as claimed.

	Thus, we are left to prove that there exists a plane drawing of the Delaunay-graph of $\F'$ with respect to $S$ such that for each edge $pq$ its drawing lies inside $F'_{pq}$. We will prove this by drawing the edges one-by-one using Lemma \ref{lem:transversaledge}.

	We take the edges one-by-one in an arbitrary order. We draw the first edge using Lemma \ref{lem:transversaledge}. Now suppose that a subset of the edges is already drawn such that no pair of the drawn edges intersects and moreover every edge intersects the boundary of a pseudo-disk at most once (which implies that it intersects a boundary only when it is necessary, that is, when exactly one of its endpoints is inside this pseudo-disk). Note that this additional requirement holds for the first drawn edge by Lemma \ref{lem:transversaledge}.

	Suppose that the next edge we want to draw connects $x$ and $y$ and we want to draw it inside $F_{x,y}$. For an illustration of the rest of the proof see Figure \ref{fig:addingedges}.
	Draw it first using Lemma \ref{lem:transversaledge}, then $f$ intersects the boundary of any other pseudo-disk at most once. Although $f$ may intersect previously drawn edges, but only edges connecting $x$ or $y$ to some other points of $S$ as all other edges lie outside $F_{x,y}$. Take the intersection $z_x$ of $f$ with a drawing of an edge $xp$ which is farthest from $x$ along $f$ among edges of this type (or $z_x=x$ if there is no such intersection). Take also the intersection $z_y$ of $f$ with a drawing of an edge $yq$ which is farther from $x$ along $f$ and is the closest to $x$ among edges of this type (or $z_y=y$ if there is no such intersection). Now take the curve $f'$ which goes from $x$ to $z_x$ along the already drawn $xp$ (very close to and on the appropriate side) on which $z_x$ lies, then goes along $f$ to $z_y$ and then goes from $z_y$ to $y$ along the already drawn $yq$ (again very close to and on the appropriate side) on which $z_y$ lies. By appropriate sides we mean that we choose sides such that $f'$ does not intersect the edges $xp$ and $yq$. This gives a drawing $f'$ of the edge $xy$ which does not intersect any earlier edge.

	We need to prove that $f'$ lies inside $F_{x,y}$. As $f$ lies inside $F_{x,y}$, we only need to care about the two parts that are drawn along the drawings of the edges $xp$ and $yq$. Yet by induction these edges were drawn such that they intersect $\partial F_{x,y}$ once, and as $z_x,z_y\in F_{x,y}$, this intersection cannot lie on the parts that connect $x$ to $z_x$ and $y$ to $z_y$. That is, all three parts of $f'$ lie inside $F_{x,y}$, as required.

	\begin{figure}
		\centering
		\includegraphics[height=4cm]{addingedges.pdf}
		\caption{Adding the drawing of the edge $xy$.}
		\label{fig:addingedges}
	\end{figure}

	Now we are left to prove that $f'$ intersects the boundary of every pseudo-disk at most once.
	For this we prove that for an arbitrary pseudo-disk $F$ its boundary $\partial F$ intersects $f'$ the same number of times as it intersects $f$. Denote by $f'_x$ the part of $f'$ between $x$ and $z_x$ and by $f_x$ the part of $f$ between $x$ and $z_x$.
	As both $f_x$ and $f'_x$ can intersect $\partial F$ at most once, we get that $f'_x$ intersects $\partial F$ if and only if $f_x$ does.
	The similar statement holds for the part of $f'$ between $y$ and $z_y$.

	As the remaining (middle) parts of $f$ and $f'$ coincide, we can conclude that they intersect $\partial F$ the same number of times.
	As $f$ intersected $\partial F$ at most once, the same holds for $f'$ as well.

	We have seen that we can add an arbitrary edge.
	Repeating this process for all edges we get that the whole Delaunay-graph can be drawn in the plane as required.
\end{proof}

\


TITLE: Relatively how much energy do fluorescent light tubes take to turn on?
QUESTION [5 upvotes]: Fluorescent lights are already efficient when they’re running but I’ve heard that it takes a lot of energy to turn a fluorescent light tube on. So is it more efficient to turn off a fluorescent tube immediately when you’ve finished using it or is it better to leave it on and then wait until you’re more likely to not use it again for a while?

REPLY [4 votes]: A fluorescent light uses as much energy getting started as it des to run for 23.3 seconds.  In other words, that is a bit of a myth about leaving it on for very long.  If you’re going to be in the room and gone for less than 23.3 seconds there’s no point it on, basically.  You might as well turn it off because it uses not very much more energy.  To put that in comparison, an LED has to run for 1.28 seconds before it uses as much energy.  The good old-fashioned incandescent lamp: 0.36 seconds before it’s used as much energy it does running as it does to turn it on.


TITLE: question with integral equation
QUESTION [1 upvotes]: I want to know how did this equation come out?
$$\int_{-1}^{\infty}\dfrac{(\cos x)^{2n}}{2^x}dx=\sum^{\infty}_{k=0}\frac{1}{2^{k\pi}}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(\cos x)^{2n}dx.$$
I hope you can give me some ideas, thank you！

REPLY [1 votes]: If I am not mistaken, this does not seem to be an identity but an approximation.
Since
$$\int_{-\frac{\pi}{2}}^{+\frac{\pi}{2}}\cos ^{2 n}(x)\,dx = \frac{\sqrt{\pi }\,\, \Gamma \left(n+\frac{1}{2}\right)}{n!}\qquad \text{and} \qquad
\sum^{\infty}_{k=0}\frac{1}{2^{k\pi}}=\frac{2^{\pi }}{2^{\pi }-1}$$ the rhs is just
$$\text{rhs}=\frac{2^{\pi }}{2^{\pi }-1}\frac{\sqrt{\pi }\,\, \Gamma \left(n+\frac{1}{2}\right)}{n!}$$
On the other hand, the antiderivative appearing in the lhs is a real nightmare. Given by a CAS
$$\int\dfrac{\cos ^{2 n}(x)}{2^x}\,dx=-\frac{2^{-x} \left(1+e^{2 i x}\right) \cos ^{2 n}(x) \, _2F_1\left(1,n+\frac{1}{2}
   i \log (2)+1;-n+\frac{1}{2} i \log (2)+1;-e^{2 i x}\right)}{\log (2)+2 i n}$$ I gave up trying to compute the values at the integration bounds and I switched to numerical integration.
The table below reproduces some results for a few values of $n$
$$\left(
\begin{array}{ccc}
 n & \text{rhs} & \text{lhs} \\
 10 & 0.6242794194 & 0.6314547539 \\
 20 & 0.4441977842 & 0.4467991375 \\
 30 & 0.3634421891 & 0.3648753657 \\
 40 & 0.3150781690 & 0.3160080393 \\
 50 & 0.2819906596 & 0.2826568587 \\
 60 & 0.2575283520 & 0.2580353046 \\
 70 & 0.2384958928 & 0.2388981010 \\
 80 & 0.2231422816 & 0.2234712982 \\
 90 & 0.2104170876 & 0.2106926026 \\
 100 & 0.1996469031 & 0.1998819199
\end{array}
\right)$$
Edit
For $n=1$, the lhs is
$$\text{lhs}=\frac{4+2\log (2) \sin (2)+\log ^2(2) (1+\cos (2))}{\log ^3(2)+4\log (2)}\approx 1.78421$$ while the rhs is $\frac{2^{\pi -1} \pi }{2^{\pi }-1}\approx 1.77154$.


TITLE: $\mathbb Q[e^{\frac{2\pi i}{3}}] \cong\mathbb Q[x]/(x^2+x+1)$
QUESTION [1 upvotes]: I want to show that the field $\mathbb Q[e^{\frac{2\pi i}{3}}] $ is isomorphic to $\mathbb Q[x]/(x^2+x+1)$. Can someone give me a hint to approach this?

REPLY [0 votes]: If $\alpha$ is any algebraic number with minimal polynomial $f$, then there is a ring homomorphism (indeed a $\mathbb Q$-algebra homomorphism)
$$\mathbb Q[X]\to \mathbb Q[\alpha]\\p(X)\mapsto p(\alpha)$$
called the evaluation map (since we are evaluating each polynomial at $\alpha$). Can you calculate the image and kernel of this map? What can you conclude?