Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 111–123
Distinguishing partitions and asymmetric
uniform hypergraphs∗
M. N. Ellingham , Justin Z. Schroeder
Department of Mathematics, 1326 Stevenson Center
Vanderbilt University, Nashville, TN 37240, USA
Received 30 June 2010, accepted 30 October 2010, published online 23 March 2011
Abstract
A distinguishing partition for an action of a group Γ on a set X is a partition of X that
is preserved by no nontrivial element of Γ. As a special case, a distinguishing partition of a
graph is a partition of the vertex set that is preserved by no nontrivial automorphism. In this
paper we provide a link between distinguishing partitions of complete equipartite graphs
and asymmetric uniform hypergraphs. Suppose that m ≥ 1 and n ≥ 2. We show that an
asymmetric n-uniform hypergraph with m edges exists if and only if m ≥ f(n), where
f(2) = f(14) = 6, f(6) = 5, and f(n) = blog2(n + 1)c + 2 otherwise. It follows that
a distinguishing partition of Km(n) = Kn,n,...,n, or equivalently for the wreath product
action Sn WrSm, exists if and only if m ≥ f(n).
Keywords: Complete equipartite graph, distinguishing number, distinguishing partition, asymmetric
uniform hypergraph.
Math. Subj. Class.: 05C25, 05C65, 20B25
1 Introduction
A coloring of the vertices of a graph G, c : V (G) → {1, 2, . . . , r}, is said to be r-
distinguishing if there are no nontrivial color-preserving automorphisms of G. The dis-
tinguishing number D(G) of G is the smallest r for which such a coloring exists. Let
V (G) = {v1, v2, . . . , vn}; the coloring c(vi) = i is trivially n-distinguishing, so the dis-
tinguishing number is well-defined for all graphs. Albertson and Collins introduced these
ideas in [1]; since then this topic has been well studied (c.f. [2, 4, 7, 9, 10, 12]).
These ideas were generalized to group actions by Tymoczko in [13]. Let Γ be a group
acting on a set X . A coloring of X , c : X → {1, 2, . . . , r}, is r-distinguishing if the only
∗In memory of Mike Albertson.
E-mail addresses: mark.ellingham@vanderbilt.edu (M. N. Ellingham), justin.z.schroeder@vanderbilt.edu
(Justin Z. Schroeder)
Copyright c© 2011 DMFA Slovenije
112 Ars Math. Contemp. 4 (2011) 111–123
u v
x w
Figure 1: The automorphism (uw)(vx) preserves the partition but not the coloring.
element in Γ that preserves the coloring is the identity. For an action on a finite set X , a
distinguishing coloring exists if and only if the action is faithful (only the identity fixes all
elements of X). The distinguishing number of the action of Γ on X , denoted DΓ(X), is
the smallest r for which such a coloring exists. Thus, D(G) = DAutG(V (G)). For further
study in the setting of group actions see [5, 6, 11, 14].
Colorings of a set X are closely related to partitions. Any coloring of X gives a par-
tition of X into color classes, while any partition yields colorings by assigning a unique
color to the elements of each part. If a group Γ acts on X , each element of Γ that preserves
a coloring also preserves the associated partition, but the converse is not necessarily true.
For example, the only graph automorphism that preserves the coloring in Figure 1 is the
identity (so it is a distinguishing coloring), but the automorphism (uw)(vx) preserves the
color class partition {{u, v}, {w, x}}.
Therefore, the idea of a distinguishing coloring may be modified to give the related
but not identical idea of a distinguishing partition. A partition of X is a distinguishing
partition if the only element in Γ that preserves the partition is the identity. To state this
formally, suppose γ ∈ Γ. For any S = {x1, x2, . . . , xs} ⊆ X , let γ′(S) = {γ(x1),
γ(x2), . . . , γ(xs)}. Moreover, for any collection S = {S1, S2, . . . , St} of subsets ofX , let
γ′′(S) = {γ′(S1), γ′(S2), . . . , γ′(St)}. Then a partition S of X is distinguishing if γ ∈ Γ
and γ′′(S) = S imply that γ is the identity. In a graph, this translates to a partition of V (G)
such that there are no nontrivial automorphisms that preserve this partition.
Distinguishing partitions seem to be a natural concept, as other important ideas for
group actions, such as primitivity, are defined in terms of the effect of elements of Γ on
partitions of X . Unlike distinguishing colorings, not all faithful group actions or graphs
admit a distinguishing partition. For example, if n ≥ 2 then Kn does not. Thus, a funda-
mental question for a faithful group action or graph is whether or not it has a distinguishing
partition.
This appears to be a difficult question. In this paper we explore some general properties
of distinguishing partitions. Then we show that even for the complete equipartite graph
Km(n) = Kn,n,...,n (having m parts of size n) it is not totally straightforward to say when
it has a distinguishing partition. For a fixed n, we provide lower bounds for m and show
these are best possible. To arrive at these bounds, a connection to asymmetric uniform
hypergraphs is established.
Despite their simple structure, complete equipartite graphs are an interesting family for
our purposes because they have a high degree of symmetry that is difficult to destroy. They
are ultrahomogeneous in the sense that every isomorphism between two induced subgraphs
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 113
extends to an automorphism of the whole graph, making it very hard to distinguish one part
of the graph from another. Gardiner [8] showed that, with two small exceptions, the only
ultrahomogeneous graphs are the complete equipartite graphs and their complements.
2 Hypergraphs and Two General Properties
A hypergraph H is a triple (V (H), E(H), I(H)), where V (H) is a finite set of elements
called vertices,E(H) is a finite set of elements called edges, and I(H) ⊆ V (H)×E(H) is
the incidence relation. If (v, e) ∈ I(H), then we say the vertex v is incident with the edge
e. Often the incidence relation I(H) is presented as an incidence matrix M(H) = (mij),
with rows indexed by vertices vi and columns indexed by edges ej . The entry mij = 1
if (vi, ej) ∈ I(H), and mij = 0 otherwise. If v is incident with exactly n edges, then
we say the degree of v is n; if all vertices v ∈ V (H) have degree n, then H is n-regular.
Similarly, if there are exactly n vertices incident with an edge e, then we say the size of e is
n; if all edges e ∈ E(H) have size n, then H is n-uniform. A graph is simply a 2-uniform
hypergraph.
Define the sets EH(v) = {e ∈ E(H) | (v, e) ∈ I(H)} and VH(e) = {v ∈ V (H) |
(v, e) ∈ I(H)} (we simply writeE(v) and V (e) ifH is understood). Two vertices v1, v2 ∈
V (H) are said to be duplicate vertices if E(v1) = E(v2); similarly two edges e1, e2 ∈
E(H) are said to be duplicate edges if V (e1) = V (e2). A hypergraph is vertex-simple or
edge-simple if there are no duplicate vertices or duplicate edges, respectively.
While we define a hypergraph as an incidence structure, it is sometimes convenient
to consider a hypergraph (particularly an edge-simple one) as a set structure where we
identify the edge e with the set V (e). We will at various times consider a hypergraph as a
set structure without explicitly making the transition.
An automorphism of a hypergraphH is a pair (π, σ), where π is a permutation of V (H)
and σ is a permutation ofE(H) such that (v, e) ∈ I(H) if and only if (π(v), σ(e)) ∈ I(H)
for all v ∈ V (H) and for all e ∈ E(H). The automorphisms of H form a group un-
der composition, denoted AutH . The image of the projection (π, σ) 7→ π is denoted
AutV H , while the image of the projection (π, σ) 7→ σ is denoted AutE H . The mem-
bers of AutV H and AutE H are called vertex automorphisms and edge automorphisms,
respectively. If AutH is the trivial group, we say H is asymmetric. A pair of duplicate
vertices or edges gives rise to an automorphism that simply swaps these vertices or edges,
so an asymmetric hypergraph is necessarily vertex-simple and edge-simple.
The dual of H , denoted by H∗, is a hypergraph (V (H∗), E(H∗), I(H∗)), where
V (H∗) = E(H), E(H∗) = V (H), and I(H∗) = {(e, v) | (v, e) ∈ I(H)}. In other
words, the dual H∗ swaps the vertices and edges of H . The map (π, σ) ∈ AutH 7→
(σ, π) ∈ AutH∗ gives rise to the following observation.
Observation 2.1. For every hypergraph H , AutH ∼= AutH∗.
Many vertex properties of hypergraphs translate naturally to edge properties using the
dual construction. For example, H is n-regular if and only if H∗ is n-uniform, and H is
vertex-simple if and only if H∗ is edge-simple. In addition, we have the following lemma.
Lemma 2.2. Let H be a hypergraph.
1. If H is edge-simple, then the projection (π, σ) 7→ π is an isomorphism from AutH
to AutV H .
114 Ars Math. Contemp. 4 (2011) 111–123
2. If H is vertex-simple, then the projection (π, σ) 7→ σ is an isomorphism from AutH
to AutE H .
Proof. (1) We know the given projection is a surjective homomorphism, so it remains to
show that it is injective. Assume (π, σ1), (π, σ2) ∈ AutH are two elements that project
to π. Since (π, σ1) is an automorphism, we must have V (σ1(e)) = π(V (e)) for all e ∈
E(H). Similarly we must have V (σ2(e)) = π(V (e)) for all e ∈ E(H). But this implies
V (σ1(e)) = V (σ2(e)) for all e ∈ E(H). Since there are no duplicate edges, this means
σ1(e) = σ2(e) for all e ∈ E(H). Hence σ1 = σ2, and the projection is injective as desired.
(2) This follows by applying part (i) to H∗ and using Observation 2.1.
Suppose we have a function f : X → Y . A subset {x1, x2, . . . , xk} ⊆ X is mapped
to the subset {f(x1), f(x2), . . . , f(xk)} ⊆ Y . This induces a function f ′ : 2X → 2Y
from subsets of X to subsets of Y . Similarly f ′ induces a function f ′′ : 22
X → 22Y from
collections of subsets of X to collections of subsets of Y . Moreover, if f is injective, then
so are f ′ and f ′′. Commonly f ′ and f ′′ are just denoted by f , but for our purposes it will
be helpful to distinguish between f , f ′ and f ′′.
The notation above, together with Lemma 2.2, provides a natural way to talk about
automorphisms of a hypergraph as a set structure. If H is an edge-simple hypergraph and
(π, σ) ∈ AutH , then we must have σ = π′|E(H). Additionally, a permutation π of V (H)
is an automorphism ofH if and only if π′′(E(H)) = E(H). Equivalently, a permutation π
of V (H) is an automorphism of H if and only if π′′(E(v)) = E(π(v)) for all v ∈ V (H).
These facts will be useful in the arguments of Section 3.
Now we mention two general results, the first a positive result for both graphs and
faithful group actions, and the second a negative result just for graphs.
Theorem 2.3. Suppose |X| ≥ 3 and the action of Γ on X has distinguishing number at
most 2. Then the action has a distinguishing partition.
Proof. If the distinguishing number is 1 then any partition is a distinguishing partition.
Suppose the distinguishing number is 2 and there is a distinguishing coloring with color
classes C1, C2 where |C1| ≥ |C2|. Then |C1| ≥ 2. Thus, the partition consisting of C1
together with |C2| singletons containing the elements of C2 is a distinguishing partition,
because any automorphism preserving this partition also preserves the distinguishing col-
oring.
This is useful, because there are a number of results showing that classes of graphs
have distinguishing number 2. For example, Klavžar and Zhu and also Imrich and Klavžar
[10, 12] give conditions on cartesian products and cartesian powers under which the dis-
tinguishing number is 2; all graphs satisfying their conditions then have a distinguishing
partition.
Let G be a graph (i.e., 2-uniform hypergraph). If G is simple in the usual sense (i.e.,
edge-simple) then we will apply Lemma 2.2(i) and consider automorphisms as just permu-
tations of V (G). If uv ∈ E(G), we say u and v are adjacent and write u ∼ v. A subset of
vertices X ⊆ V (G) is a module if for every v ∈ V (G) \X , either x ∼ v for all x ∈ X or
x 6∼ v for all x ∈ X . If in addition X forms an independent set or clique, then X is called
an independent module or complete module, respectively. In general, large independent
or complete modules prevent the existence of a distinguishing partition, as shown in the
following result.
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 115
Theorem 2.4. Let G be a graph with |V (G)| = n. If G contains an independent or
complete module X with |X| > n+12 , then there exists no distinguishing partition of G.
Proof. Assume G has a distinguishing partition. To avoid an automorphism that simply
swaps two vertices in X , each vertex in X must be in a different set of the partition, and
at most one vertex in X can be in a set by itself. Thus, every other vertex in X must be in
a partition with some element not in X , so n ≥ 2|X| − 1. But this implies n+12 ≥ |X|, a
contradiction. Therefore, no distinguishing partition exists.
3 Reduction to hypergraphs
In this section we establish a connection between automorphisms of Km(n) preserving a
partition of its vertices and automorphisms of certain hypergraphs.
Let [k] denote the set {1, 2, . . . , k}. The graph Km(n) contains m induced copies of
Kn, and we can let V (Km(n)) = [m] × [n], where (i, j) denotes the jth vertex in the ith
copy of Kn. Let ρ : V (Km(n)) → [m] be the projection given by ρ(i, j) = i. In the
graph Km(n), any automorphism permutes the m copies of Kn along with independently
permuting the vertices within each Kn. Using the definitions of [3], we see that (after
reversing coordinates in V (Km(n)) = [m]× [n]) the action of AutKm(n) is just the wreath
product action Sn WrSm on the set [n]× [m], where Sk is the symmetric group acting on
[k].
The following theorem formalizes the link between asymmetric hypergraphs and dis-
tinguishing partitions of complete equipartite graphs. The idea is to project a partition of
V (Km(n)) using ρ′′ to obtain a hypergraph with vertex set [m], or, conversely, to lift a
hypergraph to obtain a partition. Intuitively it is not hard to see that the partition will be
distinguishing if and only if the hypergraph is n-regular and asymmetric, but verifying this
rigorously requires some technical arguments.
Theorem 3.1. The following are equivalent for m,n ≥ 1:
1. There exists a distinguishing partition of Km(n).
2. There exists a distinguishing partition of mKn (the union of m disjoint copies of
Kn).
3. There exists an asymmetric n-regular hypergraph with m vertices.
4. There exists an asymmetric n-uniform hypergraph with m edges.
5. There exists a distinguishing partition of the wreath product Sn WrSm acting on the
set [n]× [m].
Proof. (1)⇔(2) This follows because mKn = Km(n) and complementary graphs have the
same automorphism group.
(1)⇒(3) Assume S = {S1, S2, . . . , Sr} is a distinguishing partition for Km(n). Thus,
if α ∈ AutKm(n) such that α′′(S) = S, it follows that α = 1[m]×[n].
For every (i, j) ∈ V (Km(n)), there exists a unique k such that (i, j) ∈ Sk; define the
function gi(j) = k for all (i, j) ∈ V (Km(n)). If two distinct vertices (i, j1) and (i, j2)
both belong to Sk then there is an automorphism of Km(n) swapping these two vertices
and preserving S, which is a contradiction. Therefore, each function gi is injective. We can
define g−1i (k) precisely when i ∈ ρ′(Sk), and
(i, j) ∈ Sk ⇔ k = gi(j) ⇔ j = g−1i (k). (∗)
116 Ars Math. Contemp. 4 (2011) 111–123
Consider the set structure H obtained by setting V (H) = [m] and E(H) = ρ′′(S).
Since each gi is injective, n distinct elements of ρ′′(S) contain each i ∈ [m], and so H is
an n-regular hypergraph.
We claim that H is edge-simple, i.e., that no two distinct edges are equal as sets. Sup-
pose ρ′(Sk1) = ρ
′(Sk2). Then for every (i, ji,1) ∈ Sk1 there exists (i, ji,2) ∈ Sk2 . The
map that swaps these two elements for all i ∈ ρ′(Sk1) forms an automorphism α of Km(n)
such that α′′(S) = S. But this implies α = 1[m]×[n]; hence, Sk1 = Sk2 and k1 = k2.
Thus, H is edge-simple.
We want to show that AutH is trivial; since H is edge-simple, it will suffice to
show that AutV H is trivial. Let π ∈ AutV H . We know π′′(E(H)) = π′′(ρ′′(S)),
so we can define the permutation p on [r] by π′(ρ′(Sk)) = ρ′(Sp(k)). Set α(i, j) =
(π(i), g−1π(i)(p(gi(j)))). We claim that (1) α is well-defined, (2) ρ ◦ α = π ◦ ρ, (3)
α ∈ AutKm(n), and (4) α′′(S) = S.
For (1), it suffices to show that g−1π(i)(p(gi(j))) is well-defined. This is true if and only
if π(i) ∈ ρ′(Sp(gi(j))) = π′(ρ′(Sgi(j))), which is true if and only if i ∈ ρ′(Sgi(j)). But
(i, j) ∈ Sgi(j) by definition of gi, so this is always true, and α is well-defined. To prove
(2), note that ρ ◦ α(i, j) = ρ(π(i), g−1π(i)(p(gi(j)))) = π(i) = π(ρ(i, j)) = π ◦ ρ(i, j)
for all (i, j) ∈ V (Km(n)). We know π is a permutation of [m], so to verify (3) it suffices
to show that j 7→ g−1π(i)(p(gi(j))) is a permutation of [n] for each i ∈ [m]. We already
know gi, p, and g−1π(i) are injective, so the composition of these maps is also injective.
Since j 7→ g−1π(i)(p(gi(j))) is an injective map from [n] to [n], it must be a permutation.
Finally, consider (4). Suppose (i, j) ∈ Sk. Then α(i, j) = (π(i), g−1π(i)(p(gi(j)))) =
(π(i), g−1π(i)(p(k))) ∈ Sp(k), using (∗) twice. Thus, α
′(Sk) ⊆ Sp(k) for all k. But⋃r
k=1 α
′(Sk) = V (Km(n)) =
⋃r
k=1 Sp(k), so we must have α
′(Sk) = Sp(k) for all k,
and α′′(S) = S, as required.
From (3) and (4) it follows that α = 1[m]×[n], and from (2) we learn that π ◦ ρ =
ρ ◦ α = ρ ◦ 1[m]×[n] = ρ. Thus, π(i) = π(ρ(i, j)) = ρ(i, j) = i for all i ∈ [m], and hence
π = 1[m]. This shows AutV H is trivial, as desired.
(3)⇒(1) Assume there is an asymmetric n-regular hypergraphH with V (H) = [m]; we
know it must be edge-simple. Let the edges be denoted T1, T2, . . . , Tr, and for each i define
the distinct numbers gi(1), gi(2), . . . , gi(n) such that E(i) = {Tgi(1), Tgi(2), . . . , Tgi(n)}.
For each (i, j) ∈ [m] × [n] replace i in Tgi(j) by (i, j); each edge Tk now becomes a
set Sk ⊆ [m] × [n] = V (Km(n)). Let S = {S1, S2, . . . , Sr}; this collection partitions
V (Km(n)). We see that ρ′(Sk) = Tk for all k ∈ [r]. Let α ∈ AutKm(n) be an automor-
phism such that α′′(S) = S. We want to show α = 1[m]×[n].
We can write α(i, j) = (π(i), hi(j)), where π is a permutation of [m] and each hi is a
permutation of [n]. Then π(ρ(i, j)) = π(i) = ρ(α(i, j)), so that π ◦ ρ = ρ ◦ α. Define the
permutation p on [r] by α′(Sk) = Sp(k). For each k,
π′(Tk) = π
′(ρ′(Sk)) = (π ◦ ρ)′(Sk) = (ρ ◦ α)′(Sk)
= ρ′(α′(Sk)) = ρ
′(Sp(k)) = Tp(k).
But then π′′(E(H)) = E(H), so π ∈ AutV H . By asymmetry of H , this means π = 1[m].
Thus, p = 1[r] as well. Now for every (i, j) ∈ Sk, we have α(i, j) = (π(i), hi(j)) =
(i, hi(j)) ∈ α′(Sk) = Sp(k) = Sk. However, (i, j), (i, hi(j)) ∈ Sk implies j = hi(j). It
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 117
Figure 2: An asymmetric 2-uniform hypergraph with 6 or more edges.
follows that hi = 1[n] for all i ∈ [m], so α = 1[m]×[n]. This shows S is a distinguishing
partition for Km(n) as desired.
(3)⇔(4) This follows from considering the dual hypergraph and Observation 2.1.
(1)⇔(5) As discussed above, this action is precisely the automorphism group ofKm(n),
from which the result follows.
Henceforth we consider our problem as in Theorem 3.1(iv), in terms of asymmetric
uniform hypergraphs. Note the restriction m ≥ 1 in the theorem; this excludes trivial
asymmetric uniform hypergraphs with no edges and one or no vertices. From the uniform
hypergraph setting we are able to get a lower bound for m.
Corollary 3.2. Suppose that m ≥ 1 and n ≥ 2. If H is an asymmetric n-uniform hyper-
graph with m edges, then m ≥ dlog2 ne+ 1.
Proof. Pick any edge f . Since H is asymmetric, it must be vertex-simple, so the sets E(u)
must be distinct for all u ∈ V (f). For every edge g ∈ E(H) \ {f}, either g ∈ E(u) or g /∈
E(u). Thus, there are at most 2m−1 possibilities for E(u). Since they must all be distinct,
it follows that n = |V (f)| ≤ 2m−1. Solving this inequality yields m ≥ dlog2 ne+ 1.
The following small cases will be needed later in the paper.
Theorem 3.3.
1. There are no asymmetric 0- or 1-uniform hypergraphs with 2 or more edges.
2. There exists an asymmetric 2-uniform hypergraph with m ≥ 1 edges if and only if
m ≥ 6.
Proof. (1) This is clear.
(2) An asymmetric 2-uniform hypergraph is simply a graph in the normal sense with a
trivial automorphism group. It is not hard to show that every graph with fewer than 6 edges
has some nontrivial automorphism. Furthermore, the tree obtained from joining copies of
the linear graphs P2, P3, and Pm−2, m ≥ 6, at a common endpoint yields anm-edge graph
with trivial automorphism group (see Figure 2).
4 The vertex and edge power complement
To define the vertex power complement HV P of an edge-simple hypergraph H , we want
to consider H as a set structure, so assume e = V (e) for all e ∈ E(H). Let V (HV P ) =
V (H), and let E(HV P ) = 2V (H) \ E(H), where 2V (H) is the power set of V (H). This
yields an edge-simple hypergraph HV P with the same vertex set as H and |E(HV P )| =
118 Ars Math. Contemp. 4 (2011) 111–123
2|V (H)| − |E(H)|. Moreover, if H is n-regular, then HV P is (2|V (H)|−1 − n)-regular.
Since H and HV P are edge-simple, we have for any permutation π of V (H)
π ∈ AutV H ⇔ π′′(E(H)) = E(H)
⇔ π′′(E(HV P )) = π′′(2V (H) \ E(H)) = 2V (H) \ E(H) = E(HV P )
⇔ π ∈ AutV HV P ,
which, together with Lemma 2.2(1), leads directly to the following observation.
Observation 4.1. For every edge-simple hypergraphH , AutH ∼= AutV H = AutV HV P
∼= AutHV P .
We can now define the edge power complement HEP of a vertex-simple hypergraph H
by HEP = ((H∗)V P )∗. In other words, we swap the vertices and edges, find the vertex
power complement, then reverse the vertices and edges back to their original roles. If we
think of our hypergraph in a slightly unusual way, identifying vertices with sets of edges,
then V (HEP ) = 2E(H) \ V (H) and E(HEP ) = E(H). Moreover, if H is n-uniform,
then HEP is (2|E(H)|−1 − n)-uniform. As with the vertex power complement, the edge
power complement preserves the automorphism group.
Corollary 4.2. For every vertex-simple hypergraph H , AutH ∼= AutE H = AutE HEP
∼= AutHEP .
Proof. This follows from Lemma 2.2(2), Observation 2.1, and Observation 4.1.
Example 4.3. HV P and HEP can be represented simply in terms of incidence matrices.
Let H be the hypergraph with incidence matrix M(H) below.
M(H) =
 1 1 01 0 0
0 1 1
 .
The hypergraph HV P is then given by the incidence matrix M(HV P ) that consists of all
binary columns not in M(H). Likewise, the hypergraph HEP is given by the incidence
matrix M(HEP ) that consists of all binary rows not in M(H).
M(HV P ) =
 0 1 0 0 10 0 1 1 1
0 0 0 1 1
 ,M(HEP ) =

0 0 0
0 1 0
0 0 1
1 0 1
1 1 1
 .
The usefulness of the edge power complement to us lies in the following corollary.
Corollary 4.4. Suppose q ≥ 0 and 0 ≤ n ≤ 2q . There exists an asymmetric n-uniform
hypergraph with q + 1 edges if and only if there exists an asymmetric (2q − n)-uniform
hypergraph with q + 1 edges.
Proof. From Corollary 4.2 we have that H is an asymmetric n-uniform hypergraph with
q + 1 edges if and only if HEP is an asymmetric (2q − n)-uniform hypergraph with q + 1
edges.
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 119
We are now able to improve the lower bound of Corollary 3.2.
Corollary 4.5. If m ≥ 1, n ≥ 3, and H is an asymmetric n-uniform hypergraph with
m ≥ 1 edges, then m ≥ blog2(n+ 1)c+ 2. Moreover, if n = 6 then m ≥ 5, and if n = 14
then m ≥ 6.
Proof. We have 2q−1 + 1 ≤ n ≤ 2q , with q ≥ 2. The bound from Corollary 3.2 is
m ≥ q+ 1, which is identical with the bound here except when n = 2q or 2q− 1, or 2q− 2
with q = 3 or 4 (i.e., n = 6 or 14). In those cases the bound here is m ≥ q + 2, so we
must show that H cannot have q+ 1 edges. If H did have q+ 1 edges then we could apply
Corollary 4.4 to obtain a 0-, 1- or 2-uniform asymmetric hypergraph with q + 1 edges,
contradicting Theorem 3.3.
5 Constructions for n = 2q, 2q − 1, 2q − 2
Corollary 4.4 presents part of an inductive construction for asymmetric uniform hyper-
graphs. However, Theorem 3.3 leaves some holes in this inductive process, so we will need
constructions for n = 2q and n = 2q − 1 for all q ≥ 2. Additionally, we need special
constructions for n = 3, 6, and 14.
Lemma 5.1. If n = 2q for q ≥ 2, then there exists an asymmetric n-uniform hypergraph
with q + 2 edges.
Proof. Let V (H) be all possible binary (q + 1)-tuples x = (x0, x1, x2, . . . , xq), and set
Si = {x ∈ V (H) | xi = 1}, 0 ≤ i ≤ q. Let T = S0 = {x ∈ V (H) | x0 = 0}. We have
|Si| = |T | = 2q for all i. Furthermore, |Si ∩ Sj | = 2q−1 for all i 6= j, |Si ∩ T | = 2q−1 for
all i ≥ 1, and |S0 ∩ T | = 0. For 1 ≤ k ≤ q− 1, let v(k) ∈ T be the vertex with v(k)k = 1
and v(k)` = 0 for all ` 6= k; also, let w(k) /∈ T be the vertex with w(k)0 = 1, w(k)` = 0
for 1 ≤ ` ≤ k−1, andw(k)` = 1 for k ≤ ` ≤ q. Set T ′ = T \{v(1), v(2), . . . , v(q−1)}∪
{w(1), w(2), . . . , w(q−1)}. SetE(H) = {S0, S1, . . . , Sq, T ′}. We claim the set structure
H is an asymmetric 2q-uniform hypergraph with q + 2 edges. The uniformity and size of
E(H) are clear from construction. To show there are no automorphisms, we consider each
edge’s intersection with T ′. To get from T to T ′ we replaced q− 1 vertices with v(k)0 = 0
with q − 1 vertices with w(k)0 = 1, so that |S0 ∩ T ′| = q − 1. For i ≥ 1, v(k)i = 0 and
w(k)i = 1 for 1 ≤ k ≤ i−1, while v(k)i = w(k)i for k ≥ i, so that |Si∩T ′| = 2q−1+i−1.
Since 2q−1 + i− 1 > q − 1 for all i ≥ 1 and q ≥ 2, the size of the intersection Si ∩ T ′ is
unique for every edge Si. T ′ is the only edge to have all unique intersection sizes, so any
automorphism of H must fix T ′. But this also fixes every Si according to the size of its
intersection with T ′. Thus, there are no nontrivial edge automorphisms of H . Since H is
clearly vertex-simple, by Lemma 2.2(2) H is asymmetric.
Corollary 5.2. If n = 2q − 1 for some integer q ≥ 2, then there exists an asymmetric
n-uniform hypergraph with q + 2 edges.
Proof. In the construction of H above, w(1) = (1, 1, . . . , 1) is incident with every edge.
Thus, removing it creates an edge-simple (2q−1)-uniform hypergraphH−w(1) with q+2
edges. Any (vertex) automorphism π of H −w(1) can be extended to an automorphism of
H by setting π(w(1)) = w(1), so H − w(1) must be asymmetric as well.
The construction in Corollary 5.2 is valid when n = 3, but gives a hypergraph with 3
vertices of degree 1. Later we will need a hypergraph with fewer vertices of degree 1.
120 Ars Math. Contemp. 4 (2011) 111–123
Lemma 5.3. There exist asymmetric hypergraphs H as follows.
1. H is 3-uniform with 4 edges, and 2 vertices of degree 1.
2. H is 6-uniform with 5 edges.
3. H is 14-uniform with 6 edges.
Proof. For each proof below, the transpose of the incidence matrix, M(H)T , is given.
The columns (vertices) are indexed by v1, v2, . . . , v2n, where n = 3, 6 and 14, respec-
tively, and the rows (edges) are indexed by e1, e2, . . . , em, where m = 4, 5, and 6, re-
spectively. To prove the induced hypergraph H is asymmetric, the sizes of the edge inter-
sections are provided in a second matrix A = (aij), with aij = |ei ∩ ej | (alternatively,
A = M(H)TM(H)). If two rows (edges) ei and ej have a different multiset of intersec-
tion sizes, then there can be no (edge) automorphism σ such that σ(ei) = ej . If all rows
of A consist of distinct multisets, then the automorphism group is trivial. This covers parts
(ii) and (iii) below, while an additional argument is needed for part (i).
(1)
M(H)T =

1 1 1 0 0 0
1 1 0 1 0 0
1 0 0 1 1 0
0 0 1 1 0 1
 , A =

3 2 1 1
2 3 2 1
1 2 3 1
1 1 1 3
 .
FromA it might still be possible for an edge automorphism to swap e1 and e3. However, e3
contains a vertex of degree 1, while e1 does not; thus, no such automorphism exists. Note
that v5 and v6 are the vertices of degree 1.
(2)
M(H)T =

1 1 1 1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 1 1 1 0 0 0
1 1 0 1 0 0 1 1 0 1 0 0
1 0 0 1 1 0 1 0 0 1 1 0
1 0 0 0 0 0 1 1 0 1 1 1
 ,
A =

6 3 3 3 1
3 6 4 2 3
3 4 6 4 4
3 2 4 6 4
1 3 4 4 6
 .
(3)
M(H)T =

1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 1 1 1 1 0 0 0
1 1 0 0 1 0 0 1 1 0 0 1 1 0
1 0 1 0 0 1 0 1 0 1 0 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1 1 1 0 0 0 0
1 0 0 1 1 0 0 1 1 0 1 1 0 0
1 1 0 1 0 1 0 1 0 1 1 0 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1 1
 ,
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 121
A =

14 7 8 7 6 1
7 14 7 6 7 7
8 7 14 7 8 7
7 6 7 14 7 8
6 7 8 7 14 9
1 7 7 8 9 14
 .
6 Main result
Our overall argument proceeds by induction on n, but for each n we also need to apply
induction on m, as provided by the following lemma.
Lemma 6.1. Suppose that m ≥ 1 and n ≥ 2. If there exists an asymmetric n-uniform
hypergraph with m edges and at most n − 1 vertices of degree 1, then there exists an
asymmetric n-uniform hypergraph with m′ edges for all m′ ≥ m.
Proof. Let H be an asymmetric n-uniform hypergraph with m edges and vertices v1, v2,
. . . , vk of degree 1, where k ≤ n − 1. We may assume H has no vertex of degree 0 (any
such vertex may be deleted). Form the edge e = {w, v1, v2, . . . , vk, x1, . . . , xn−k−1},
where w /∈ V (H), and the xi’s are any other distinct vertices in V (H). The hypergraph
H + e contains only one vertex of degree 1, namely w. The edge e containing w must
be fixed under any automorphism, and it follows that any edge automorphism of H + e
must also be an edge automorphism of H . Thus, the only automorphism of H + e is the
trivial one, and we have an asymmetric n-uniform hypergraph with m + 1 edges. Since
we now have only one vertex of degree 1, we can repeat this process to get an asymmetric
n-uniform hypergraph with m′ edges for all m′ ≥ m.
Remark 6.2. Since a vertex-simple hypergraph with m edges can have at most m vertices
of degree 1, the degree 1 requirement holds automatically for m ≤ n− 1.
Theorem 6.3. Let m, n be integers with m ≥ 1 and n ≥ 2. There exists an asymmetric
n-uniform hypergraph with m edges if and only if m ≥ f(n), where:
f(n) =

6 if n = 2
5 if n = 6
6 if n = 14
blog2(n+ 1)c+ 2 if n > 2, n 6= 6, 14
Proof. The case n = 2 is covered by Theorem 3.3(2). For n ≥ 3, applying Corollary 4.5
and Lemma 6.1 means it suffices to find such a hypergraph for m = f(n) with at most
n − 1 vertices of degree 1. Since f(n) ≤ n − 1 for all n ≥ 5, Remark 6.2 says we can
ignore the degree 1 requirement except when n = 3 or 4. We proceed by induction on n.
Note that for 3 ≤ k ≤ n we always have f(k) ≤ f(n).
Case 1. If 2q−1 + 1 ≤ n ≤ 2q − 2 with q ≥ 3 and n 6= 6 or 14, then let n = 2q − k
with 2 ≤ k ≤ 2q−1 − 1 < n. Since f(k) ≤ f(n) (when k = 2 this follows because n 6= 6
or 14), by the inductive assumption there exists an asymmetric k-uniform hypergraph with
f(n) = q + 1 edges. Applying Corollary 4.4 provides the desired n-uniform hypergraph.
Case 2. The cases n = 6 and 14 follow from Lemma 5.3(2) and (3).
122 Ars Math. Contemp. 4 (2011) 111–123
Case 3. If n = 2q − 1 with q ≥ 3, then the result follows from Corollary 5.2.
Case 4. If n = 3, then the result follows from Lemma 5.3(1).
Case 5. If n = 2q with q ≥ 2, then the result follows from Lemma 5.1. Note that for
n = 4 the construction produces only 3 vertices of degree 1.
This exhausts all cases and completes the proof.
Corollary 6.4. Let m, n be integers with m ≥ 1 and n ≥ 2, and let f(n) be defined as in
Theorem 6.3.
1. There exists a distinguishing partition of Km(n) if and only if m ≥ f(n).
2. There exists a distinguishing partition of mKn if and only if m ≥ f(n).
3. There exists an asymmetric n-regular hypergraph with m vertices if and only if m ≥
f(n).
4. There exists a distinguishing partition for the wreath product Sn WrSm acting on
[n]× [m] if and only if m ≥ f(n).
Proof. Apply Theorem 3.1 to Theorem 6.3.
7 Final comments
An obvious next step would be to try to extend our main result to other complete multi-
partite graphs. Dealing with all complete multipartite graphs may be difficult, so it may be
sensible to focus on some special classes.
If we fix m, there are only finitely many complete m-partite graphs with a distinguish-
ing partition. Arguments similar to those elsewhere in this paper show that a distinguishing
partition has at most 2m − 1 parts, and each part has size at most m, so if the total number
of vertices is large there cannot be a distinguishing partition. (Better bounds on the number
of vertices could be obtained, but we just wish to establish the general idea.) For example,
for complete bipartite graphs it is not hard to show the following.
Proposition 7.1. The only complete bipartite graphKr,s, 1 ≤ r ≤ s, with a distinguishing
partition is K1,2.
It therefore seems more interesting to look at complete multipartite graphsKn1,n2,...,nm
with arbitrarily large m, but where n1, n2, . . . , nm take only a small number of distinct
values.
Acknowledgements
The first author would like to thank Tom Tucker for helpful conversations, and we thank
Melody Chan for providing references [11, 14].
References
[1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3
(1996), #R18.
[2] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283
(2004), 29–35.
M. N. Ellingham and J. Z. Schroeder: Distinguishing partitions. . . 123
[3] P. J. Cameron, Permutation Groups, in Handbook of Combinatorics, Vol. 1, Elsevier, Amster-
dam, 1995, 611–645.
[4] M. Chan, The distinguishing number of the augmented cube and hypercube powers, Discrete
Math. 308 (2008), 2330–2336.
[5] M. Chan, The distinguishing number of the direct product and wreath product action, J. Alge-
braic Combin. 24 (2006), 331–345.
[6] M. Chan, The maximum distinguishing number of a group, Electron. J. Combin. 13 (2006),
#R70.
[7] M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs,
Discrete Math. 308 (2008), 2240–2246.
[8] A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976) 94–102.
[9] W. Imrich, J. Jerebic, and S. Klavžar, The distinguishing number of Cartesian products of
complete graphs, European J. Combin. 29 (2008), 922–929.
[10] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53
(2006), 250–260.
[11] S. Klavžar, T.-L. Wong, and X. Zhu, Distinguishing labellings of group action on vector spaces
and graphs, J. Algebra 303 (2006), 626–641.
[12] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, Euro-
pean J. Combin. 28 (2007), 303–310.
[13] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11 (2004),
#R63.
[14] T.-L. Wong and X. Zhu, Distinguishing labeling of group actions, Discrete Math. 309 (2009),
1760–1765.