ars mathematica contemporanea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 45-66 Distinguishing partitions of complete multipartite graphs Michael Goff Vanderbilt University, Department of Mathematics, 1326 Stevenson Center, Nashville, USA Received 2 January 2013, accepted 23 February 2014, published online 27 May 2015 Abstract A distinguishing partition of a set X with automorphism group aut(X) is a partition of X that is fixed by no nontrivial element of aut(X). In the event that X is a complete multipartite graph with its automorphism group, the existence of a distinguishing partition is equivalent to the existence of an asymmetric hypergraph with prescribed edge sizes. An asymptotic result is proven on the existence of a distinguishing partition when X is a complete multipartite graph with m1 parts of size n1 and m2 parts of size n2 for small n\, m2 and large m1, n2. A key tool in making the estimate is counting the number of trees of particular classes. Keywords: Complete multipartite graph, distinguishing partition, combinatorial species, tree enumeration. Math. Subj. Class.: 05C25, 05C65, 20B25 1 Introduction The distinguishing partition problem asks, given a finite set X with a group G that acts on X, whether there exists a partition P of the elements of X such that no nontrivial element of G fixes P. Formally, consider a partition P = {P1,... ,Pt} and 7 G G. For general X' = {xi,...,xi} c X, let y(X ') = {7(xi),... ,7(xj)}. Then let 7(P) = {7^),..., 7(Pt)}. We say that P is a distinguishing partition if 7(P) = P for all nontrivial 7 G G. When X is a graph, we consider it to be acted upon by its automorphism group aut(X). Not all sets X with group action G have a distinguishing partition. For example, if G is the group of all permutation on X and |X | > 2, then X does not have a distinguishing partition. Conversely, if G is the trivial group, then all partitions of X are distinguishing. As another example, let X be the set {a, b, c, d} acted upon by the cyclic group with E-mail address: michael.goff@vanderbilt.edu (Michael Goff) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 46 Ars Math. Contemp. 10 (2016) 31-44 generator that takes a to b, b to c, c to d, and d to a. Then X has the following distinguishing partitions: {{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}}, {{a, b}, {c}, {d}}, {{b, c}, {d}, {a}}, {{c, d}, {a}, {b}}, {{d, a}, {b}, {c}}. By contrast, the dihedral group acting on four elements has no distinguishing partition. In general, the conditions for the existence of a distinguishing partition can be quite complex, even in a relatively restricted setting such as taking X to be a complete multipartite graph, acted upon by its automorphism group. Informally, the difficulty is that if a partition P consists of few large parts, then a nontrivial automorphism might fix each part, while if P consists of many small parts, then a nontrivial automorphism might permute the parts. Ellingham and Schroeder [7] first considered the distinguishing partitions problem for complete equipartite graphs. Their finding is that if X is a complete equipartite graph with m parts, each of size n, then X has a distinguishing partition if and only if m > f (n) for f (2) = f (14) = 6, f (6) = 5, and otherwise f (n) = |>g2(n + 1)J + 2. In this setting, aut(X) is the imprimitive action of the wreath product Sn I Sm on X. The distinguishing partition is a measure of the level of symmetry of a group action, and as such the concept is closely related to the well-studied distinguishing number, as introduced by Albertson and Collins [1] on a graph and by Tymoczko [11] for a general group action. Other such measures are the cost of 2-distinguishing [6] and the determining set [5]. The survey of Bailey and Cameron [2] shows how these concepts have appeared independently in many different settings. The distinguishing number of X is the mimimum number of label classes in a distinguishing labeling of X. In turn, a distinguishing labeling is a map from X to the set of labels [t] that is not fixed under any nontrivial automorphism of X. All distinguishing partitions can be regarded as distinguishing labelings by treating each block of the partition as a separate label class, but not all distinguishing labelings are similarly distinguishing partitions. Every set with group action has a distinguishing labeling-every element could be assigned a unique label-but not all have a distinguishing partition. It should be noted that the term "distinguishing partition" has been used elsewhere to mean what we here call a distinguishing labeling. For the remainder of this paper, we will consider the case that X is a complete multipartite graph with its automorphism group. We denote by X = Kni,...,nm the complete multipartite graph with maximal independent sets X; of size n; for 1 < i < m. Also, Km1(n1),m2(n2) denotes the complete multipartite graph with m; parts each of size n; for i = 1,2. We focus in particular on Kmi(ni),m2(n2) for fixed n1 and m2 and large mi and n2 . Based on the results of Ellingham and Schroeder [7], we might expect a complete multipartite graph to have a distinguishing partition if it has many small parts, and not to have a distinguishing partition if it has few large parts. In our setting, which combines these two extremes, it seems natural to expect that a distinguishing partition, in the asymptotic sense, would exist if n2/m1 does not exceed a certain ratio. Our main result is that this is indeed the case. Theorem 1.1. Fix n1 > 2 and m2 > 1, and suppose that m1 is sufficiently large relative to n1 and m2. There exists a value r = rni,m2 such that the following holds. Kmi(ni),m2(n2) has a distinguishing partition if and only if n2 < rni,m2m1 + e(m1) Michael Goff: Distinguishing partitions of complete multipartite graphs 47 for some function e(mi) G o(mi). We have that r2,m2 = 1. For n1 > 3, we define rni,m2 by first choosing values of j = jni,m2 and k = k^,^ such that m2 ni =2 + V 0 + m-2 + ••• + m2 + k, with either j< L(m2 - 1)/2J and 0 < k< m2 j + 1 or j = L(m2 - 1)/2J and k > 0. If j < L(m2 - 1)/2J, then let i + E m2 — if m2 N m2 — j — 1 +--k, m2 i m2 and otherwise choose 1+ j ■ / \ 1 m2 - i m2 1 ¿=0 m2 i + - k. + 2 We say that j2,. -1. The structure of the paper and the proof Theorem 1.1 is as follows. In Section 2, we establish basic concepts on enriched trees and hypergraphs which are used heavily throughout the proof. In Section 3, we show how a type of partition of Kmi(ni),m2(n2) known as a regular partition may be represented as a hypergraph with mi edges of size ni, i = 1,2. We establish key lemmas for the general result in Section 4. In Section 5, we provide the general construction that, for the existence of a distinguishing partition, maximizes n2 to within an additive constant, given m1, h1, m2. Then we prove that for large m1 relative to h1 and m2, if n2 > n2 and Kmi(ni),m2(n/) has a distinguishing partition, then so does Kmi(ni),m2(„2). In Section 6, we focus on the case that h1 = 2. Then the following refinement of Theorem 1.1 holds. Theorem 1.2. There exist constants a > 0 and ft > 1 and f m-1 (ft - 1) _ ^3/2 V aft "" such that Theorem 1.1 holds with e(m1) of the form z := (logß mi) mi zrr + (1 + omi (1))aßzz-7/2(ßA_ mi ß - 1) logß(mi)' In Section 7, we consider the case that k = 0 and j < |_(m2 - 1)/2j. Then Theorem 1.1 can be refined as follows. Theorem 1.3. If k = 0 and j < |_(m2 — 1)/2j, then Theorem 1.1 holds with e(m1) of the form / 2m2 — 4 j — 5 \ / (2m2 — 4j — 4) 2m2-4j-^2 i \ 2m2—4j—4 -C 2m2—4j—4 + om, (1) m-, 2 J I 2m2 — 4j — 5 + mi () / 1 for a value of C that depends only on h1 and m2. 1 j r = r 2 48 Ars Math. Contemp. 10 (2016) 31-44 The value of C will be specified in Section 7. We consider k > 1 and j < |(m2 - 1)/2J in Section 8. Theorem 1.4. If k > 1 and j < |(m2 — 1)/2J, then Theorem 1.1 holds with e(mi) of the form ©(mi/(log mi)). In Section 9, we consider the case that k = 0 and j = (m2 — 2)/2. Then the following exact result for large mi is possible. Theorem 1.5. Suppose that k = 0 and j = |_(m2 — 1)/2J. Theorem 1.1 holds with e(mi) = 2m2-i if m2 is even and at least 4 and e(mi) = 2m2-i — 1 if m2 isoddor 2, for sufficiently large mi. In Section 10, we prove the following for k > 1 and j = |_(m2 — 1)/2j. Theorem 1.6. If k > 1 and j = |_(m2 — 1)/2j, then Theorem 1.1 holds with e(mi) = 2m2-i — 1 if kmi is even and m2 is odd, and otherwise e(mi) = 2m2-i + |rmiJ — rmi, for sufficiently large mi. 2 Enriched trees and hypergraphs Combinatorial species and enriched trees We make use of the language of combinatorial species, as presented by Bergeron, Labelle, and Leroux [4]. A species F is, for every finite set U, a finite set of objects F[U], called structures, together with, for every bijection a : U ^ U', a function F[a] : F[U] ^ F[U'] that satisfies the following two properties, which are standard functioriality properties in category theory: 1) for all bijections a : U ^ U' and a' : U' ^ U", F[a' o a] = F[a'] o F[a], 2) for the identity map Idy, F [Idy ] = IdF u]. The function F[a] is known as transport of species. Consider the symmetric group Sy that acts on U. Given an F-structure s, we say that the automorphism group of s, aut(s), is the subgroup of those a G Sy that satisfy F[a](s) = s. Let a be the species of asymmetric trees, or trees whose automorphism group is trivial, and let a* be the species of rooted asymmetric trees. A rooted tree is considered asymmetric if it has no nontrivial root-preserving automorphism; it is possible that the underlying unrooted tree structure is not asymmetric. Now let F be a species that contains at least one structure over a set of size 1. An F-enriched tree on a set U is a tree on U together with an F-structure sv on the neighbor set N (v) of every vertex v G U .If a is an automorphism of an F-enriched tree t, then a is an automorphism of the underlying tree structure of t. Furthermore, if av is the restriction of a on N(v), then the transport of species F[av] takes sv to sCT(v). We say that aF is the species of asymmetric F-enriched trees. For example, when F is E, the species of sets, then there is a unique E-structure on every finite set, and aE is simply a. The species A and AF are, respectively, the species of (not necessarily asymmetric) trees and the species of F-enriched trees. The sum of two species (F + F')[U] is the disjoint union F [U] + F'[U] such that (F + F')[a](s) = F[a](s) if s G F[U] and (F + F')[a](s) = F'[a](s) if s G F'[U]. If a Michael Goff: Distinguishing partitions of complete multipartite graphs 49 is a positive integer, then aF is the sum of a copies of F. We say that Fj[U] is F [U] when |U| = i, and otherwise Fj [U] = 0, and |Fj | is the number of structures of F over a set with i elements. Consider the species F = J2f=i a» E for nonnegative integers k, ai,..., aK with k > 1 and ai > 1. This is the species that consists of a» distinct set structures over a set with i elements for 1 < i < k and otherwise no structures. Then the species aF may be regarded as the species of asymmetric trees in which every vertex has degree at most k, and every vertex of degree i is assigned a label from a pool of a» possible labels. Such a tree is asymmetric if it has no nontrivial label-preserving automorphism. Later, we show how estimating the number of elements of aF with a given number of vertices can help determine asymptotic bounds for the distinguishing partitions problem. A structure of the product species FF' over U is an ordered pair (f, f') for an F-structure f over Ui anda F'-structure f' over U2 for some partition Ui l_lU2 of U. Transport of species is defined by (FF')[a](s) = (F[ai](f), F'[a2](f')), each a» the restriction of a to Uj. Hypergraphs A hypergraph H is a triple (V(H), E(H), I(H)), with V(H) a finite set of elements called vertices and E(H) a finite set of elements called edges. The incidence relation I(H) is a subset of V(H) x E(H). We will generally treat edges as subsets of V(H). The degree of v € V(H), denoted deg(v), is the number of edges incident to v. H is connected if the bipartite graph with vertex sets V(H) and E(H) and edge set I(H) is connected, and E(H) = 0. If every edge is incident to ni-vertices, then H is ni-uniform. For a hypergraph H with an edge e, degi (H) and degi (e) denote the number of vertices of degree 1 in H and e, while deg+ H and deg+ e are the numbers of vertices of degree at least 2 in H and e. An automorphism a of H is a permutation of V(H) and E(H) such that (v, e) € I(H) if and only if (a(v), a(e)) € I(H) for all vertices v and edges e. We say that a is trivial if a( v) = v and a( e) = e for all vertices v and edges e, and H is asymmetric if the only automorphism of H is trivial. Thus we allow that hypergraphs may contain multiple edges that are incident to the same vertex set, but such hypergraphs are not asymmetric. A connected ni-uniform hypergraph H is called a tree if E(H) can be enumerated {ei,..., e|E(H)|} in such a way that for each 2 < i < |E(H)|, we have that |e» n (ei U • • • U ei-i)| = 1. Equivalently, a tree is a connected ni-uniform hypergraph H with (ni - 1) |E (H)| + 1 vertices. The leaves ofatree H are the edges e that satisfy degi(e) = ni - 1. We say that /(G) is the number of leaves of G. For a tree G, define the quantity M(G):= £ (deg(v) - 2). vev (G) deg(v)>2 We will later need the following relationship between /(G) and ^(G). Lemma 2.1. Let G be a tree with at least 2 edges. Then /(G) > ^(G) + 2. Proof. Enumerate E(G) = (ei,..., e|E(G)|) such that for 2 < i < |E(G)|, ei n (ei U ... U ej_i) = {vj, 50 Ars Math. Contemp. 10 (2016) 31-44 and let Gj be the subtree of G with edges (ei,..., e^. We prove that the lemma holds for Gj by induction on i for 2 < i < |E(G)|, with the i = 2 case following from ^(G2) = 0 and 1(G2) = 2. Assume the lemma holds for Gi-1. For 3 < i < |E(G)|, ^(Gj) = ^(Gj_1) + 1 if vj has degree at least 3 in Gj, and otherwise ^(Gj) = ^(Gj_1). Also, 1(Gj) > 1(Gj_1) since ej is a leaf in Gj, and at most one leaf of Gj_j, namely a leaf that contains vj as a degree 1 vertex, is not a leaf in Gj. Furthermore, whenever ^(Hj) = ^(Gj_1) + 1, vj has degree at least 2 in Gj_1 and thus 1(Gj) = 1(Gj_1) + 1. The lemma follows for Gj by 1(Gj) — 1(Gj_1) > ^(Gj) — MGi_1). □ 3 Distinguishing partitions and asymmetric hypergraphs We demonstrate a bijection between certain distinguishing partitions of complete multipartite graphs and asymmetric hypergraphs with prescribed edge sizes. Using this bijection, we establish the existence or nonexistence of distinguishing partitions by demonstrating the existence or nonexistence of certain asymmetric hypergraphs. The argument is nearly identical to that given by Ellingham and Schroeder [7]. With X = Knii...,nm, let P be a partition of X with parts P^ ..., Pt, and we say that P is a regular partition of X if |Xj n Pj/1 < 1 for all i and i'. It is a necessary but not sufficient condition for P to be distinguishing that P is regular. Definition 3.1. For every regular partition P of X with parts P1,..., Pt, we associate a hypergraph t(P) as follows: V(t(P)) = {Pj, 1 < i < t}, E(t(P)) = {Xj : 1 < i < m}, and Xj and Pj/ are incident if |Xj n Pj/1 = 1. Note that t (P) is a hypergraph with m edges with sizes n1,..., nm since Xj intersects exactly nj parts of P. We say that the automorphism group aut(P) is the subgroup of aut(X) consisting of those elements that fix P. The following relationship holds. Lemma 3.2. If P is a regular partition of X, then aut(P) is isomorphic to aut(T (P)). Proof. Let f : aut(P) ^ aut(T (P) be the group homomorphism induced by t. Say that P1,..., Pt are the parts of P. An automorphism a e aut(P) induces automorphisms aP and aX on the sets {Pj} and {X } respectively. Then a is uniquely determined by aP and aX, and in particular a is trivial if and only if aP and aX are both trivial. Thus f is injective. Now let a' e aut(T(P)). Then a' is uniquely determined by incidence-preserving permutations of {Pj} and {Xj/}. Let a be the permutation of X such that if x e X is the unique vertex contained in Xj n Pj', then a(x) is the unique vertex contained in a'(Xj) n a'(Pj'). It is readily checked that in fact a e aut(P), and thus f is surjective. □ Corollary 3.3. There exists a distinguishing partition of Knii...,nm if and only if there exists an asymmetric hypergraph with m edges of sizes n1,..., nm. It will be convenient to associate another hypergraph with a regular partition P of Kmi(ni),m2(n2). Let t'(P) be a vertex-labeled hypergraph that contains exactly the vertices and the n1-edges of t(P). Say that the n2-edges of t(P) are X1,..., Xm2. Then the vertex label set of t'(P) is 2[m2], and a vertex v in t'(P) is labeled with a set S C [m2] if v e Xj exactly when i e S. Then t'(P) is just a different way of encoding t(P). Michael Goff: Distinguishing partitions of complete multipartite graphs 51 The weight w(v) of a vertex v e t'(P) is the cardinality of its label. The weight w(S) of a set of vertices S is the sum of the weights of the vertices in S. The weight w(e) or w(G) of an nx-edge e or connected component G c t'(P) is the weight of the vertex set of e or G. The value of G is w(G) - rm2 |E(G) |. Value may be positive or negative. We have that n2 = w(t'(P))/m2, and thus our strategy in proving the main results is to find an asymmetric labeled hypergraph with mx nx-edges and maximal weight. Though weight and value encode the same information, value is useful in that it gives a clear comparison of the weight of a component of t'(P) to its asymptotic limit. 4 Key Lemmas We now present a series of lemmas that provide upper bounds on the weights and values of certain types of components. Lemma 4.1. Let G be a connected n1-uniform hypergraph with nx|E(G)|/2 + p vertices. Then G contains 2p + ^(G) vertices of degree 1. Equivalently, each edge has, on average, (2p + ^(G))/|E(G)| degree 1 vertices. Proof. There are nx|E(G)| pairs of the form (v, e), where v is a vertex, e an edge, and v e e. The number of such pairs (v, e) is also degi(G) + 2(ni|E(G)|/2 + p - degi(G)) + ^(G), or ni|E(G)| + 2p - degx(G) + ^(G). Thus degx(G) = 2p + ^(G). □ Lemma 4.2. Suppose that t(P) is asymmetric, and let S be the set of degree 1 vertices in an edge of t'(P). Then |S| < 2m2. Define nonnegative values j' and k' such that |S| = em02) + • • • + e72) + k' with either 0 < k' < e^) or k' = 0 and j' = m2. Then w(S) < ]T(m2 - i) (m2) + k'(m2 - j' - 1). i=0 ^ % ' Proof. For all vx, v2 e S, there is an automorphism of the underlying unlabeled hypergraph of t'(P) that switches vx and v2 and fixes all other vertices. Thus all vertices in S must have different labels in t'(P), which implies that |S| < 272. The lemma follows from the fact that S contains at most (72) vertices with a label of cardinality m2 - i. □ Let W|S| denote the upper bound on w(S) in Lemma 4.2. Now suppose that t'(P) is asymmetric and G is a component of t'(P). A defect in G is one of the following. A defective vertex is a vertex v with degree at least 2 and weight less than m2, counted with multiplicity d(v) = m2 -w(v). A defective edge is an edge e with set S of degree 1 vertices with collective weight less than w|S|, counted with multiplicity d(e) = w|S| - w(S). The number of defects in G is denoted by d(G). Lemma 4.3. Let G be a connected component of t'(P). If t(P) is asymmetric, then w(G) < m2 deg+(G) + ^ (e) - d(G). e£E(G) 52 Ars Math. Contemp. 10 (2016) 99-112 Proof. Every vertex has weight at most m2, and a defective vertex v with degree at least 2 has weight m2 - d(v). The set of degree 1 vertices in an edge e has weight wdegl(e) if e is not defective, and otherwise weight wdeg (e) - d(e). The lemma follows by adding over all vertices. □ If G contains n |E(G)|/2 + p vertices, then write 2p + ^(G) = b 2p + m(G) |E(G)| + b' 2p + m(G) |E(G)| with nonnegative b + b' = |E(G)|. The following lemma states that the weight of G is maximized when all edges have about the same number of degree 1 vertices. Lemma 4.4. With all quantities as above, w(G) < m2n1|E(G)|/2 — m2p — m2^(G) + bw 2p+m(g) 1 + b'wr— d(G). L |E(G)| J I |E(G)| I Proof. By Lemma 4.1, G has n1 |E(G) |/2 — p — ^(G) vertices of degree at least 2. Then by Lemma 4.3, w(G) < m2ni|E(G)|/2 — m2p — m-2^(G) + ^ wdegl(e) — d(G). e£E(G) The expression is concave in y, meaning that for all y, — wy-1 > wy+1 — . Thus, given a set of values jyj} such that J2i yi = 2p + ^(G), is maximal when b of the yi are equal to 2p+M(G) |E(G)| and b' of the yi are 2p+M(G) |E(G)| . The lemma follows. □ We now look to maximize the weight of G by considering the total number of vertices of a given weight. In particular, G contains at most |E(G)|(™2) degree 1 vertices with weight m2 - i, since each each edge contains at most (™2) such vertices. Choose values j* and k* such that 2p + M(G) = |E(G)| (m^) + ■ ■ ■ + |E(G)I (^J*2 I + k* with j* > —1 and 0 < k* < |E(G)|(j.m+1). Lemma 4.5. With all quantities as above, w(G) < mzi— p — + j |E(G)|(m2 — i)' m2 2 =0 i + (m2 — j * — 1)k* — d(G). Proof. Let G' be a (not necessarily asymmetric) hypergraph constructed from G by giving every vertex of degree at least 2 the label [m2] and assigning a label to every degree 1 vertex such that all edges of G' are nondefective and have distinct labels among the degree 1 vertices. Then G' has (ni|E(G)|/2 - p - ^(G)) vertices of degree at least 2, each of which has weight m2, and at most |E(G)|(™2) degree 1 vertices of weight m2 - i for 0 < i < j*. The result follows by w(G') = w(G) + d(G). □ Michael Goff: Distinguishing partitions of complete multipartite graphs 53 We consider the upper bound of Lemma 4.5 to be a function wmax(p, ^(G), d), with the quantities m2 and |E(G) | considered to be fixed. We note that Wmax(P, M(G), d) > Wmax(p, /«(G), d + 1), while Wmax(p, M(G), d) > Wmax(p, ^(G) + 1, d), with equality exactly when j * = -1. Now we consider ^(G) = d = 0, and the upper bound of Lemma 4.5 is a function wmax(p). The effect of replacing p by p +1 is equivalent, numerically, to replacing a vertex with weight m2 by two vertices, one of weight m2 - j * - 1 and the other of weight either m2 - j * - 1 or m2 - j * - 2. Thus the function wmax(p) is weakly unimodal in p and achieves a maximum when j * = |_(m2 - 1)/2j and k* =0 or 1. Then 2p = Ei=7-1)/2j |E(G)|(7) +(0 or 1), and we have by Lemma 4.5 that m2-1j ^m2-1j \ mfi - T E (?) +^b(m2 - i)(7) J. (4.1) Thus the following holds. Corollary 4.6. Let all quantities be as above. 1. If j = |(m2 - 1)/2j, then w(G) < m2r|E (G)|. 2. If j < |(m2 - 1)/2j and p < |E(G)|( ^r - 1), then w(G) < m2r|E(G)|. 3. G has positive value only if j < |_(m2 - 1)/2j and G is a tree. Then if G has d defects, v(G) < m2 - 2j - d. Proof. Part 1 follows by Equation (4.1) and the definition of r. Part 2 follows from the monotonicity of wmax and the definition of r. Part 3 is a consequence of Parts 1 and 2. □ We now focus on the particular case that G is a tree and k = 0. Suppose that G has l leaves, and by Lemma 2.1, l > ^(G) + 2. Then j* = j and k* = 2 + ^(G), and £ Wdegi(e) < £ |E(G)|(m2 - i)(m2) +(M(G)+2)(m2 - j - 1). e£E(G) i=0 V i / This bound can be attained if G contains |E(G)| (™2) degree 1 vertices of weight m2 - i for 0 < i < j and ^(G) + 2 degree 1 vertices of weight m2 - j - 1. However, every leaf of G contains a vertex of weight at most m2 - j - 1, and thus in fact J2eee(g) wdegl (e) < £ |E(G)|(m2 - i) (+ (m(G) + 2)(m2 - j - 1) - (l - m(G) - 2). i=0 ^ i ' Since G has |E(G) | - 1 - ^(G) vertices of degree 2 or more, w(G) < m2|E(G)| + £ |E(G)|(m2 - i) (- MG)j + m2 - 2j - l. i=0 i Finally, if we allow that G might have d defects, then we conclude the following. 66 Ars Math. Contemp. 10 (2016) 99-112 Lemma 4.7. With all quantities as above, v(G) < m2 — 2j — l — j^(G) — d. Now we consider all of t'(P). Let Comp(P) be the set of connected components of T '(P ). Lemma 4.8. If t(P) is asymmetric, v(t'(P)) < ^geComp(P) v(G) + m22m2-1. Proof. We calculate that v(t'(P)) is ^geComp(P) v(G) plus the sum of the weights of all vertices not contained in any n1-edge. Since t (P) is asymmetric, every vertex not contained in an «4-edge must have a different label, and there is at most one vertex with every label S c 2[m2]. The lemma follows. □ 5 An extremal construction In this section, we give a general method of constructing a distinguishing partition P of Kmi(ni),m2(„2). We then show that n2 is maximal to within an additive constant, given the other parameters. We do so by describing the vertex-labeled hypergraph t'(P). For the remainder of this section, we assume that j < |_(m2 — 1)/2J; the case that j = |_(m2 — 1)/2J is treated seperately. Let G be a component of t'(P). Define the value v(e) of an edge e G E(G) to be v(G)/|E(G) |. Let £ be the map that adds 1 mod m2 to every element in the label of every vertex of a 2[m2]-vertex labeled hypergraph. Note that v(£(G)) = v(G). Say that vertex labeled hypergraphs G, G' are equivalent under if G = £j(G') for some i. Let T* = T* m2 = (71,72,...) be an ordered list of equivalence classes under of positive weight asymmetric hypergraphs such that the edges in an element of T have value at least as great as the edges in an element of 7i+1 for all i. By Lemma 4.7, an edge e may have value S > 0 only if e is contained in a tree with at most m2/S edges. Thus T* enumerates all hypergraphs with positive value, and only classes of trees are in T*. A symmetry breaking loop R is a 2[m2]-vertex labeled hypergraph on at least minR = minR(n1, m2) edges defined as follows. If m2 = 1, then j = —1 and n1 = 2, and we set minR = 6. Let R be a cycle that contains consecutive vertices v1, v2, v3, v4. Then all vertices of R have weight 1 except for v1, v2, v4, which all have weight 0. If m2 > 1, we set minR = max(2m2, n1 + 1). Let quotR be the maximum multiple of m2 up to |E(R) |. Let v0,..., vquot _1 be vertices and e0,..., equot _1 be edges such that ej contains only degree 1 vertices (ixcept for Vj, vi+1, subscripts mocfquotR. The set of vertex labels of the degree 1 vertices of e0 includes all possible labels of size at least m2 — j, and all others are of size m2 — j — 1. To determine the labels of the degree 1 vertices of ej, add i mod m2 to every element in the labels of the degree 1 vertices of e0. Assign v0 the label 0, vj the label [m2] — i for 1 < i < m2, and vj the label [m2] for all other i. Finally, R contains edges of the form vj, vj+1,..., vj+ni_1 for 1 < i < |E(R)| — quotR. We need some key facts on symmetry breaking loops. Lemma 5.1. Let R be a symmetry breaking loop that is a component of t'(P). Then no automorphism of P induces a nontrivial automorphism of R. Proof. The lemma is readily verified when m2 = 1, and so we assume that m2 > 1. Let a be an automorphism of t (P) that induces an automorphism of R. Since v0 is the only vertex of R of weight 0, it is a fixed point. Since v1 is the only vertex of R that is in a common edge with v0, has degree 2 in t'(P), and weightnot equal to m2, v1 is also a fixed Michael Goff: Distinguishing partitions of complete multipartite graphs 66 point. Thus all v are fixed, which implies that a fixes the n2-edges of t (P). Since all v are fixed, a thus also fixes all n -edges of R. Finally, since all degree 1 vertices in a given edge have different labels, they must be fixed points as well. □ The following is readily observed from the construction of symmetry breaking loops. Lemma 5.2. Let R be a symmetry breaking loop, and let 1 < i < i' < m2. Then the number of vertices of R whose label contains i is equal to the number of vertices of R whose label contains i'. Lemma 5.3. There exists a value w = wni,m2, which depends only on n1 and m2, such that a symmetry breaking loop R has value at least w. Proof. If m2 = 1, then v(R) = -3. If m2 > 1, then the total weight of the degree 1 vertices in each edge with degree 1 vertices is m2(r - 1). All other vertices have weight m2 except for m2 vertices of weight m2 - 1 and one of weight 0. It follows that w(R) = quotRm2r - 2m2 and v(R) = -(|E(R)| - quotR)m2r - 2m2 > -m2r - 2m2. □ We now come to our construction of P. Choose Z to be the maximum value such that the total number of edges in all trees of T1U • • • U Tz is at most m 1 - minR. Let Ami (ni) ,—2 be the union of all trees in T1 U • • • U Tz, together with a symmetry breaking loop so that Ami(ni),m2 has m1 edges, and a degree 0 vertex of every label except 0. Lemma 5.4. Ami(ni),m2 is in fact t ' (P) for a distinguishing partition P for an appropriate value of n2. Proof. By construction, Ami(ni),m2 contains the same number of vertices whose label contains i as the number of vertices whose label contains i' for all 1 < i < i' < m2. Thus Ami(ni),m2 is t'(P) for some partition P of Kmi(ni),m2(n2) and for some n2. Next, we apply Corollary 3.3 and show that P is distinguishing by showing that t(P) is asymmetric. Let a be an automorphism of t(P). Since Ami(ni),m2 contains exactly one symmetry breaking loop, all n2-edges of t(P) are fixed under a. Since all components of Ami(ni),m2 are asymmetric and no two are isomorphic to each other, all n1-edges and vertices of t (P) are fixed as well. □ Next, we prove that Ami(ni),m2 is a nearly optimal construction. Lemma 5.5. Let P be a distinguishing partition of Kmi(ni),m2(n2) such that t'(P) = Ami(ni),m2, and let G' be an asymmetric vertex-labeled hypergraph. Then w(G') < w(Ami(ni),m2) + Errorni,m2 for some value Errorni,m2 that depends only on n1 and m2. In particular, if P' is a distinguishing partition of Kmi(ni),m2(n/), then n2 < n2 + Error„i,m2 /m2. Proof. First we determine an upper bound on w(G') in terms of the structure T*, and then we compare that to w(Ami(ni),m2). Let be the sum of the weights of all vertices of G' that are not contained in edges; since they must all have different labels, < m22m2-1. Then, summing over all components G of G' that contain n1-edges, n2 < ^^ J2a w(G) + 2m2-1 = rm1 + -1- Ee£E(a') v(e)+2m2-1. 2 67 Ars Math. Contemp. 10 (2016) 99-112 Suppose that the set of edge values of hypergraphs in T* are {vi, v2,...} with v1 > v2 > • • •, and suppose that there are nv» total edges in all hypergraphs of T* with value v». Let p be the largest value such that t'(P) contains nvp edges of value vp. Then p / p \ w(G') < rmim2 + ^nvjvj + mi - ^nv» Vp+i + m22m2 1. j=1 V j=1 / Now we consider t'(P) with symmetry breaking loop R. Choose Z so that Tq is the last equivalence class of trees that are components of t'(P); edges in 7Z+i have value vp+1, and thus by Lemma 4.7, each tree in 7P+i has at most m2/(vp+1) edges. By construction, R has at most m2/(vp+1) + minR edges, each of which has value at least w/|E(R)|. Furthermore, t'(P) contains nv» edges of value v» for 1 < i < p, and all edges besides these and edges in R have value vp+1. Thus w(Ami(ni),m2) > rmim2 + ^nvjvj + |mi - ^nv^ Vp+i - |E(R)| - jE(Ry^) + m22m2 1. Thus w(G') — w(Ami(ni ),m2) < |E(R)|(vp+i — w/ |E(R)|) < m2 + minR vp+i — w. This proves the lemma. □ In the subsequent sections, we prove upper bounds on n2 in terms of the other variables by evaluating the weights of Ami(ni),m2. For every m1, n1, m2, choose n2(m1, n1, m2) maximally so that Km^m),^^) has a distinguishing partition Pmi(ni),m2. Lemma 5.6. limm, __.no n?(mi'i"i,m2\ = 1. n2(mi + 1,ni,m2) Proof. It follows by construction of Ami (ni ),m2 and Lemma 5.5. □ Lemma 5.7. If m1 is sufficiently large relative to m2,n1, and n2, then Kmi(ni),m2(n2) has a distinguishing partition. Proof. If n2 is small relative to n1 and m2, then an asymmetric hypergraph with m» edges of size n for i = 1, 2 may be constructed as follows. First take an asymmetric hypergraph with m1 n1-edges, which exists by the main result of [7]. Then add m2 n2-edges on the same vertex set. The result is asymmetric. □ Now assume that n2 is large. Choose m* maximally so that n2 = n2(m*, n1, m2) > n2. By Lemma 5.6, n2/n2 is close to 1. We need to show that Km»(ni),m2(„2) has a distinguishing partition. Our method is to show that there exists distinguishing partition P' of Km*(ni ),m2(n'2) and a subset S of weight m2 vertices on t'(P'), with |S| = n2 - n2, such that the hypergraph that results by changing all of the labels of vertices of S from [m2] to 0 is asymmetric. Lemma 5.8. With all quantities as above, V (t '(P')) has a subset S of weight m2 vertices of size n2 - n2 such that the hypergraph G' that results from changing all labels of vertices of S from [m2] to 0 is t '(P *) for a distinguishing partition P * of Km»(ni),m2(„2). Michael Goff: Distinguishing partitions of complete multipartite graphs 68 Proof. Certainly P* is a partition of Km»(ni) m2(„2). It suffices to show that S may be chosen so that t (P*) is asymmetric. If t'(P') contains ©(n2) vertices of degree at least 2 of weight m2 and none of weight 0, then any set S of size n2 - n2 of weight m2 and degree at least 2 vertices satisfies the desired property. This condition is seen directly in all cases that j = |_(m2 - 1)/2J, as P' is constructed directly in subsequent sections. It must be that t'(P') has few components with weight 0 vertices, and no components with many weight 0 vertices. Otherwise, if n = 2, we could replace all those components and a largest defect-free component of t'(P'), if there is one, by a single defect-free asymmetric tree, which would increase the weight, a contradiction to Lemma 5.5. Otherwise, we could replace all those components and a largest symmetry breaking loop of t'(P'), if there is one, with a single symmetry breaking loop. By Lemma 4.7 if n = 3, and otherwise by Corollary 4.6, this would increase the weight, also a contradiction to Lemma 5.5. It is shown in subsequent sections that for all sufficiently large t, there is an element of T* with t edges. Thus there are ^(Vm*) elements of T* of size up to 2^m7 that are not components of t'(P'). It must be that all but o(m*) edges of t'(P') are contained in positive weight components; otherwise, all components with nonpositive weight could be removed and replaced by ^(Vm*) components of positive weight, a contradiction to Lemma 5.5. Let Ti,..., Ta be the components of t'(P') with weight 0 vertices. Let T be a positive weight component with t vertices. Then T has ©(t) vertices of degree at least 2, all but at most m2 of which have weight m2, and thus t'(P') has ©(m*) vertices in positive weight components with weight m2. Let S be a subset of size n2 - n2, chosen uniformly at random, of the weight m2 vertices that are contained in the larger half of positive weight components. Let G' be the hypergraph that results from changing the labels of all vertices of S in t'(P') from [m2] to 0. Every component T of G' that contains a vertex of S is asymmetric, since it was constructed by dividing the set of vertices labeled [m2] into vertices labeled [m2] and 0, and it had no vertex labeled 0 previously. T is not isomorphic to another component T' that contains a vertex of S since the hypergraph that results from changing all vertices of T of label 0 to [m2] is nonisomorphic to the hypergraph that results from changing all vertices of T' of label 0 to [m2]. To conclude, we need to show that with high probability, Ti is not isomorphic to any component of G' for each 1 < i < a, since a is small. If Ti is isomorphic to T, a component of G' that contains a vertex of S, then it must be that the hypergraphs Ti* and T* , which result from converting all vertices of Ti and T of label 0 to [m2], are isomorphic. Thus Ti* is isomorphic to a component T* of t'(P'). Since T* is asymmetric, for all subsets S' of weight m2 vertices of T*, the hypergraphs that result from converting all vertices of S' from label [m2] to 0 are nonisomorphic. Since T* is large, the probability that T is isomorphic to some other component of G' is small. □ Lemma 5.9. Suppose that Km»(ni) m2(„2) has a distinguishing partition and m1 > m*. Then Kmi(ni),m2(n2) has a distinguishing partition. Proof. It suffices to prove the lemma for m1 = m* + 1. Let P be a distinguishing partition of Km»(ni) m2(„2). Define a tail T of t(P) to be a sequence of vertices v1;..., vni+i-1 and edges {v,..., vni+i-1} for 1 < i < t, such that vni,..., vni +t_1 are contained in no edges outside of T. Assume that T is chosen so that t is maximal. Then add an vertex v„i+i and an edge {vt+1,..., v„i+i} to t(P) to create a hypergraph G'. 69 Ars Math. Contemp. 10 (2016) 99-112 We show that G' is asymmetric. By construction, vni+t is the only degree 1 vertex contained in a maximum tail of G', and thus it is a fixed point. Then the edge {vt+1,... ,vni+i} is fixed, since it is the only edge to contain vni +t. Thus all other vertices and edges are fixed as well, since t(P) is asymmetric. It follows that Kmi(ni),m2(n2) has a distinguishing partition. □ We summarize the preceding lemmas as follows. Corollary 5.10. If m1 is large relative to n1 and m2, let «2 be the largest value such that Kmi(ni)tm2(n>2) has a distinguishing partition. Then Kmi(ni),m2(n2) has a distinguishing partition if n2 < n'2. 6 ni = 2 In this section we consider the case that n1 = 2. A labeled connected 2-uniform hypergraph has positive value only if it is a tree with fewer than m2 defects. Furthermore, all trees without defects have positive value. Our bounds and construction requires an estimate on the number of asymmetric ordinary trees, which is provided by the twenty-step algorithm of Harary, Robinson, and Schwenk. Lemma 6.1. There exists constants a > 0 and ft > 1 such that the number of asymmetric trees on i edges is (1 + Oj(1))aft®i-5/2. Furthermore, there exists a' > 0 such that the number of asymmetric rooted trees on i edges is (1 + Oj(1))a'ft®i-3/2. Proof of Theorem 1.2: Recall that f mi (ft - 1) , n 3/2^ /m1(ft - 1) , n3/2\ log4(log-) Summing the result of Lemma 6.1 from 1 to z, the number of nonisomorphic asymmetric trees with at most z edges is (a+ o(1))ftzz-5/2, and they collectively have (a+ o(1))ftzz—3/2 < (1 + o(1))m1 edges. Similarly, the collective number of edges of nonisomorphic asymmetric trees with at most z +1 edges is at least (1 + o(1))m1, and with at most z + 2 edges exceeds m1. Each edge of a defect-free tree on z + 2 edges has value m2/(z + 2), and thus all edges of Ami(ni),m2 have value at least m2/(z + 2), except edges in the symmetry breaking loop. ( \2 We show that Ami(ni),m2 has z+j + (1 + omi (1))aftzz-7/2 ( -—A components of value m2 and o(ftzz-7/2) = o(m2/z2) components of lesser value. The latter statement follows by Lemma 6.2. Thus in fact Ami(ni),m2 contains (1 + Oj(1))a'ft®i-3/2 defect-free components on i edges for 1 < i < z, o(m1/z) defect-free components on z + 2 edges, o(m1/z2) components of other types, and all remaining components are defect-free on z + 1 edges. For every edge e G E(Ami(ni),m2), let v*(e) = v(e) - m2/(z + 1). For 1 < i < z, the sum of v* (e) over all edges e in components with z + 1 - i edges is thus (m2 + o(1))aftz+1-i(z + 1 - i)-3/2(1/(z +1 - i) - 1/(z + 1)). Michael Goff: Distinguishing partitions of complete multipartite graphs 70 By «zz 7/2 = ©(mi/log2 mi), the preceding sum is m2a«z+1-iz-3/2(i/z2) + o(mi(0-7 log2 mi) for i < z/ log z, and otherwise m2a«z+1-iz-3/2(i/z2) + o(m1/ log3 m1), which is observed by noting that «z-z/logz = O((m2 log(m1)3/2)1-1/ logz), and that m1/ logz > m1loglogmi/logmi = log4(m1) for all fixed i. The sum of v* (e) over all edges e in components with either z + 2 edges or with defects is o(m 1 / log2 (m 1)), whereas v * (e) = 0 if e is in a defect-free component with z +1 edges. We conclude that z ^ v*(e) = a«zz-7/2 ^ «-i(i +1) + o(m1/ log2 m1) eeE(r'(P)) i=0 «2 = a«zz-7/2 « + o(m1/ log2 m1). (« - 1)2 Thus ^ v(e) = 7+1 + a«Zz-7/2 («^1)2 + 0(^1/log2 m1), e£E(r '(P)) z + (« ) which implies that G has the desired number of components of value m2. The proof of Lemma 6.2 makes use of the species L(a*) of ordered sets of rooted asymmetric trees: an element of L(a*) on z' elements is given by order partitioning [z'] into subsets and taking an a*-structure on each subset. Lemma 6.2. There are o(m1/z2) components of Ami(ni),m2 with defects. Proof. If G is a component of Ami(ni),m2 with a defect, then the value of G is at most m2 - 1, and thus since the edges of G have value at least m2/(z + 2), then G has at most mm-1 (z+2) edges. Thus we need to show that the number of components with defects on at most mm-1 (z + 2) edges in Ami(ni),m2 is o(«Zz-9/2). It suffices to show that the number of components with positive value on z' edges is O((«')z ) for fixed « < «' < «m2/(m2-1) and z' < mm-1 (z + 2), since «z' < «z/z4 for fixed i. If G is a component of positive value with z' edges, then by Lemma 4.7 all but at most m2 - 1 vertices of G are labeled [m2]. Let G' be the subgraph of G that is the union of all paths between vertices not labeled [m2]. Only vertices not labeled [m2] are leaves in G', and each leaf has one of 2m2 - 1 labels, and thus the number of such G' that may result is at most a polynomial in z', say p(z'). We may reconstruct G from G' by replacing every vertex v G G' with a rooted asymmetric tree with root v. Thus, since G is determined by G' and an ordered set of asymmetric trees on a total of z' + 1 vertices, there are at most p(z')|L(a* )z'+1| components on z' edges. Choose fixed « < «* < «'. The lemma follows by showing that |L(a*)z'+1| = O((«*)z ). We show inductively on z' that |L(a*)z'+1| ^ y(«*)z for some sufficiently large 7. 71 Ars Math. Contemp. 10 (2016) 99-112 Note the recursion L(a*) = E0 + a*L(a*): every ordered set of rooted trees is either the empty set or a rooted tree followed by another ordered set of rooted trees. Thus for z' > 1, |L(a*)z'+i| = ]T |a*||L(a*)z'+i-i| < E |a'|7(£T'+i-i. i=i i=i Let a z'-3/2(1 + o(1)) E l«**^ i=i i=i Lz'/3J Lz'/3J E I a* |ß-i < 1 + o(1) and E KKß*)-i <ß/ß*. i=i i=i Thus£Z=+1 |a*|Y(ß*)z'+1-i < Yß(ß*)z' + E Iail7(ß*)z'+1- i=lz'/3j + i z' + 1 * \ z' + i (£*)z' + (1 + o(1)) E a'^ii-3/27(^*)z'+i-i <7(,T) i= lz'/3j + i as desired. □ 7 k = 0 and j < [(m2 - 1)/2J In this section we consider the case that k = 0 and j < |(m2 - 1)/2j. The value of C defined in the statement of Theorem 1.3 is determined as follows. If 0 < j < m2/2 - 3/2, then m2 C Vj + V \jJ I m2 - 2j - 3 J (2m2 - 4j - 4)!. If j = 0 and m2 > 3, then C = mm2-i A2m2 - 4A_1_ C = m2 U2 - 3 J (2m2 - 4)!' m2-2j-Vm2\ m2-2j-3f 2m2 - 4j - 4\ 2-m +2j+3 Michael Goff: Distinguishing partitions of complete multipartite graphs 72 and if j = m2/2 - 3/2, then C = Q^) ((j"+21) - l) /2. The result requires the following estimate on the number of structures of a particular type of tree. Lemma 7.1. If i is odd, the number of labeled struc(ures ofAEl+£3 on i + l vertices is ((¿-11/2) 2(i-1>/2, and of Aei+2E3 on i + l vertices is ((i!+)1/2) (i - l)!. Proof. Apply Proposition 3.1.19 of Bergeron, Labelle, and Leroux [4]. □ Proof of Theorem 1.3: We start by proving an upper bound on the sum of the values of all components of Ami(ni) ,m2. Let G be a component of Ami(ni) ,m2 with t edges and positive value; by Lemma 4.7, G is a tree with at most m2 - 2j - l leaves. Construct a colored graph c(G) from G as follows: V(c(G)) is the union of all edges of G and vertices of G of degree at least two; and E(c(G)) is given by vertex-edge containment. Every defective vertex or edge in G is colored red in c(G) .If v is a non-defective vertex of degree at least 3, then v is colored green in c(G). All other vertices of c(G) are blue. A segment in c(G) is a maximal path (v0,..., vj) such that for all 0 < i' < i, vi> is a blue vertex with degree 2. Construct a new graph c'(G) by replacing every segment (v0,... ,vi) with a single edge v0vi, and label that edge by the number i of edges itreplaces in c(G). The number of edges of c'(G) is at most 2m2 - 4j - 5. To see this, observe that G has d defects and at most m2 - 2j - l - d leaves by Lemma 4.7. Every leaf of c'(G) is a leaf of G. Combining the facts that ^vev(c'(g)) deg(v) = 2e(c'(G)) and ^vev(C'(c))(deg(v) -2) = -2, e(c'(G)) < 2m2 - 4j - 5 - 2d + a - b, where a and b are the number of vertices of degree 2 and at least 4 in c'(G). However, the only degree 2 vertices in c'(G) correspond to defects in G, and thus a < d. Thus c'(G) has at most 2m2 - 4j - 5 edges. Furthermore, this bound is attained only if G has m2 - 2j - l leaves, no defects, no vertices of degree at least 4, and no vertices of degree 3 if j > 0 by Lemma 4.7. If c'(G) has 2m2 - 4j - 5 edges, then G has value l and no edges that intersects four other edges, since this would give a vertex of degree at least 4 in c'(G). Thus, if c'(G) has 2m2 - 4j - 5 edges, then c'(G) has m2 - 2j - l leaves and m2 - 2j - 3 vertices of degree 3. If j > 0, then by Lemma 4.7, all vertices of c'(G) are blue, and such trees, forgetting labels, may be described by the species As1+s3. If j = 0, then the degree 3 vertices may be green or blue, and thus such trees are described by the species AEl+2E3. Given c'(G) with i = 2m2 - 4j - 5 > 2 edges and that G has t edges, there are (l+o1(t))ti-1/((i-l)!a) nonisomorphic labellings of the edges, where a is the cardinality of the automorphism group of c'(G). This is since that in most labellings, all labels are distinct, and the orbit of a labeling with distinct labels consists of a labellings. The number of labeled graphs c' (G) of a given isomorphism class and automorphism group of order a is (i + l)!/a. Hence the number of graphs c(G) with c'(G) having m2 - 2j - l leaves is Y(l + o1(t))ti-1/((i - l)!(i + l)!), where 7 is the number of labeled specimens of as in Lemma 7.1. If c'(G) has fewer than i = 2m2 - 4j - 5 edges, there are o(ti-1) labeling of c'(G). Since the number of graphs c'(G) that may arise is independent of t, the total number of graphs c(G) is 7(l + o1(t))ti-1/((i - l)!(i + l)!), of which almost all have m2 - 2j - l leaves and all segments of different lengths. 73 Ars Math. Contemp. 10 (2016) 99-112 Given a graph G', the number of components G of Ami (ni ),m2 with positive value such that c(G) = G' has an upper bound that depends only on n and m2. G is determined by c(G) and the following: the labels of all defective vertices, the labels of all vertices that are contained in defective edges, the labels of all vertices contained in leaves of G, and the labels of all vertices contained in edges with at least 3 vertices of degree at least 2. There are at most m2 - 2j - 1 of each of these items in G, and each one may be determined in at most 2nim2 ways, and thus there are at most 24nim2(m2-2j-1) components G with positive value such that c(G) = G'. Thus, there are o(t2m2-4j-6) positive-value components G with t edges such that either G has at most m2 - 2j - 2 leaves or c'(G) has two edges with 2 m 2 — 4 j — 5 the same label. Adding over all t, there are o(mim2—4j—4) such components G. Now we determine how many positive-value components G with t edges of Ami (ni ),m2 satisfy these two conditions: c(G) = G' for a particular graph G' with m2 - 2j - 1 leaves, and c'(G) has distinct edge labels. If 0 < j < m2/2 - 3/2, G has no defects, no vertices of degree at least 3 (if j > 0), and m2 - 2j - 3 edges that intersect 3 others. Each leaf, since it is not defective, contains one vertex of every label S with |S| > m2 - j and exactly one vertex with a label S with |S| = m2 - j - 1. There are (.,"+1) ways to select this label. Each edges that intersects 3 others, since it is not defective, contains a vertex of every label S with |S| > m2 - j except for one label S with |S| = m2 - j. There are ("j2) ways to choose this label. The total number of such components is Q"21)m2 2j ^"j2)"2 2j 3, and the distinct edge labels of c'(G) ensure that each of these components are asymmetric. If j = m2/2 - 3/2, then c(G) has 2 leaves and is a path. As before, the two leaves each contain a vertex of every label S with | S| > m2 - j, together with one vertex each of labels S and S' respectively with |S| = |S'| = m2 - j - 1. All other edges contain exactly a vertex) of each label S with |5| > m2 - j .By asymmetry, S = S'. Thus there are (j"+21)((."+21) - 1)/2 asymmetric components G with c(G) = G'. We conclude that there are (C + o(1))t2m2-4j-6 components of Ami(ni),m2 with t edges and positive value, almost all of which have value 1 and none with value exceeding m2 - 2j - 2. Adding over all i t< (1 + 0(1))(m1 (2m2 - 4j - 2m2—4j—4 proves the result. 8 k > 1 and j < |(m2 - 1)/2J Proof of Theorem 1.4: We start with the upper bound on n2. By Lemma 4.7, every component of Ami(ni),m2 has value at most m2 - 1, and every component with positive value is a tree. Suppose that the number of components of Ami(ni),m2 on i edges with positive value is at most 6® for some 6. Then Ami(ni),m2 has at most fer(logb(mi'1/21+i-1 components with at most [log6(m1)/2] edges. Thus, Ami(ni),m2 has at most fer(logb("bi))1/21+i-1 + \\ogJmn )/2 components of positive value, each of which has value at most m2 - 1. This would prove the upper bound. We now establish that there are at most 6® components of positive value on i edges for some 6. Every component G of positive value is a tree. Associate with G a labeled tree G' as follows. The vertex set of G' is the union of the edge set of G and the set of vertices Michael Goff: Distinguishing partitions of complete multipartite graphs 74 of G with degree at least 2. The edges of G' are given by inclusion in G. If v is a vertex of G' that corresponds to a vertex of G, then v is given the same label; thus, there are at most 2m2 possible labels for v. If e is a vertex of G' that corresponds to an edge of G, then e is labeled in a way to encode the number and labels of degree 1 vertices of e. Thus e can be labeled in at most 1 + 2mi + 22mi + • • • + 2"2™1 ways. G can be reconstructed to isomorphism from G'. If G has i edges, then G' has at most 2« — 1 vertices. Thus the number of isomorphism classes of underlying unlabeled trees of G' grows exponentially in i [10]. Since the number of possible labels of each vertex of G' depends only on ni and m2, the total number of trees G', and thus components G, grows at most exponentially in i. To prove the lower bound on n2, we show that the number of components of Ami (ni ),m2 with t edges does in fact grow exponentially in t. Let G be a tree without defects or vertices of degree at least 3 such that every edge contains at least ("2) + • • • + ("j2) degree 1 vertices. Then G contains 2|E(G)| — 1 vertices of weight m2, |E(G)| ("j2) of weight m2 — i for 1 < i < j, and |E(G) |k + 2 of weight m2 — j — 1. Then G has value m2 — 2j — 2. To G we may associate a vertex-labeled tree G', with the vertices of G' given by the edges of G, and the edges of G' are given by intersection. The label of a vertex of G' encodes the labels of the degree 1 vertices of the corresponding edge. Suppose that such an edge e intersects i other edges. Since e contains a vertex of every label with of size at ( m2 \ . least m2 — j and k — i + 2 vertices of label of size m2 — j — 1, there are a4 := ((++2) ways to label e in G'. Thus G' may be regarded as a member of a^k+2 a e , and from every member of this species, one can reconstruct an asymmetric 2"-labeled ni-uniform tree with positive value. We show that |(a^k+2 a e )t| grows exponentially in t by exhibiting a subset of structures of exponential size. Let (v0,..., v^2t/3j) be a path. Let S be subset of size t — 1 — |2t/3j of the integers from 3 to |_2t/3j — 2 that includes 3 and |_2t/3j — 2. For every i G S, let u be a vertex with an edge w^. Then the graph with vertices (v0,..., v^2t/3j) and u for each i G S, and labels chosen arbitrarily, is an element of a^k+2 a e . Two such graphs are nonisomorphic for different choices of S, and the number of choices of S grows exponentially in t. Say that there are trees of the maximum possible value of m2 — 2j — 2 on t edges for some fixed b and sufficiently large t. Then Ami(ni ),m2 contains no component with more than [log6(mi)] edges for large mi, except possibly the symmetry breaking loop, and Ami (ni ),m2 has at least mi -m2rri'o0gSib((;"1i)]1 -minR components. This proves the theorem. 9 k = 0 and j = |(m2 - 1)/2J We consider Theorem 1.5 in three cases. Theorem 9.1. Theorem 1.5 holds for even m2 > 4. Proof. The upper bound on n2 follows from Lemmas 4.7 and 4.8: when j = (m2 — 1)/2, since every tree has at least 2 leaves, no component has positive value. We establish the that n2 may be rmi +2"2-i by the following construction. Let t'(P) consist of components Gi,..., Gm2 of ni-edges, such that Gj consists of tj edges, and all the tj are distinct and sum to mi. Say that Gj contains edges ei,..., eti such that for all 1 < a < b < tj, ea and eb do not intersect unless b = a + 1, in which case ea n eb = {va}. Each va is labeled [m2]. Each ea contains one vertex of each of label of size at least m2 — j. 75 Ars Math. Contemp. 10 (2016) 99-112 In addition, e1 and eti contain respective vertices u1 and u2 of labels {i, i + 1,..., i + j} and {i, i — 1,..., i — j}, subscripts mod m2. In addition, t'(P) contains one degree 0 vertex of each nonempty label. Now we show that t(P) is asymmetric. Since the Gi have different numbers of edges, no automorphism permutes the components of t'(P) nontrivially. The only nontrivial automorphism of the edges of Gi reverses the chain. Given that an automorphism a fixes the n2-edges of t(P), the two leaf edges of Gi cannot be interchanged, and thus are fixed and all edges of Gi are fixed. Thus every degree 2 vertex in t'(P) is fixed as well. Finally, each degree 1 vertex in an edge e g Hi has a different label, and thus all these vertices are fixed. Finally, since a fixes each Gi componentwise, and the n2-edge Xi intersects Gi more than any other n2-edge, a fixes each n2-edge. □ Theorem 9.2. Theorem 1.5 holds when m2 = 2. Proof. All components of t'(P) have a a nonpositive value by Lemma 4.7. By Lemma 4.7, if G is a tree of 0 value, then G has two leaves and is a chain. Furthermore, to assure asymmetry, the leaves of G must contain vertices labeled {1} and {2} respectively. Otherwise, if G is a non-tree with value 0, then since r = 2, G must have t edges and 2t vertices, and every vertex must be labeled [2]. We conclude that if t'(P) has value m22m2-1, then t'(P) is a collection of chains, as described above; components in which every vertex is labeled [2]; and a degree 0 vertex of every nonempty label. But then t (P) has a symmetry that results from reversing each chain and switching the n2-edges. Thus the upper bound on n2 holds. Now we prove the sufficiency of the bound by construction. Let t'(P) contain a chain with at least five edges, e1,..., emi such that ea and eb intersect only when b = a +1, and then ea n eb = {va}. All vertices are labeled [2] except for v1 and v2, which are labeled {1} and {2} respectively, and degree 1 vertices u1 and u2 that are contained in each of the leaves, labeled {1} and {2} respectively. Also, t'(P) contains a degree 0 vertex of each nonempty label. We show that t (P) is asymmetric. The n2 -edges cannot be switched since no automorphism of t'(P) moves v1 to any other vertex of weight 1. Thus v1 is a fixed point in t(P), which fixes all edges of t'(P). Furthermore, the vertices in the leaves of t'(P) are fixed since they are of different labels. □ Theorem 9.3. Theorem 1.5 holds for odd m2. Proof. By Lemma 4.7, no component of t'(P) has positive value. We establish the upper bound on n2 by showing that every connected component of t'(P) has negative value. Suppose that G is a component with value 0. ByLemma4.4, G contains |E(G)|(h1 — 1) vertices, of which |E(G) | (h1 — 2) have degree 1. Furthermore, every edge contains h1 — 2 degree 1 vertices since wni-1 + wni-3 < 2wn2-2. Construct G' by removing these degree 1 vertices. Then G' is a ordinary, 2-regular connected graph and thus a cycle. Furthermore, G lacks defects. We conclude that G has a nontrivial automorphism. Now consider the following construction when m1 > m2 + 3. Let t'(P) contain a connected n1-uniform hypergraph with edges e1,..., emi, subscripts mod m1, such that ea and eb do not intersect unless |b — a| = 1. If b = a +1, then we say that ea n eb = {va}. t'(P) has no defects except for the following. For 1 < i < m2 — 1, say that vi is labeled [m2] — {i}, and vm2+1 is labeled [m2] — {m2}. Also, t'(P) contains a degree 0 vertex of each nonempty label. Then t'(P) is asymmetric, and n2 is the maximum value. □ Michael Goff: Distinguishing partitions of complete multipartite graphs 76 10 k > 1 and j = L(m2 - 1)/2J We say J that an (0, s, t, n^-regular hypergraph if J satisfies the following conditions. J is n1 -uniform with t edges, of which all edges intersect s other edges with the exception of 0 edges that each intersect s — 1 other edges. Furthermore, no two edges intersect at more than 1 vertex, and every vertex has degree at most 2. Finally, every automorphism of J fixes all edges. Before we prove the main result of this section, we need some lemmas on the existence of regular hypergraphs. Lemma 10.1. Let 0 and s > 3 be given, and suppose that t is sufficiently large relative to 0 and s. Suppose that st — 0 is even. Then there exists an asymmetric graph with t vertices such that all vertices have degree s, except for 0 vertices that have degree s — 1. Call a graph of this form an (0, s, t)-asymmetric graph. Proof. The lemma follows from the main theorem of [9] when st is even and 0 = 0, since an random s-regular graph is almost surely asymmetric. Such a graph is also almost surely s-connected [3]. Consider the case that st is even. Then 0 is also even. Choose distinct t1,... ,t^/2 such that t1 + ... +1^/2 = t, with each tj even if t is even. For 1 < i < 0/2, let Gj be an s-connected (0, s, tj)-asymmetric graph with an edge removed. Then the disjoint union of the Gj is an (0, s, t)-asymmetric graph. For odd st and 0, we may construct a (0, s, t)-asymmetric graph as follows. Let G' be an (0(s — 1), s, t — 0)-asymmetric graph. Add new vertices v1,..., v^ to G', each with disjoint neighbor sets of size s — 1 vertices of degree s — 1 in G'. The resulting graph is (0, s, t)-asymmetric. □ Lemma 10.2. Let 0 and s > 3 be given, and suppose that t is sufficiently large relative to 0 and s. Suppose that st — 0 is even. Also let n1 > s be given. Then there exists an (0, s, t, n1)-asymmetric hypergraph. Proof. Let G be an (0, s,t)-asymmetric graph. Let H' be a hypergraph with vertex set E(G), edge set V(G), and incidence given by incident in G. Then construct H from H' by adding n1 — d degree 1 vertices to every edge in H' that contains d vertices. Then H is (0, s, t, n1)-asymmetric. □ Proof of Theorem 1.6: The upper bound on n2 follows by Corollary 4.6 and 4.8, except when km1 is even and m2 odd. In this case, suppose that all connected components of t'(P) have value 0, and t'(P) contains a degree 0 vertex of every nonempty label. By Lemma 4.4 and the fact that wni_k_1 + wni_k_3 < 2wni_k_2, every edge of t'(P) contains exactly n1 — k — 2 degree 1 vertices. Furthermore, t'(P) does not have any defects. In this case, t(P) has an nontrivial automorphism that permutes the n2-edges. The upper bound on n2 follows. We establish the result by the following constructions. First consider the case that km1 and m2 are both even. Let the graph of t'(P) be an (m2, k + 2, m1, n1)-asymmetric hypergraph, which exists by Lemma 10.2, together with a degree 0 vertex of every nonempty label. Choose the labels of the vertices of t'(P) so that there are no defects, label the edges with k + 1 degree 1 vertices by e1,..., em2, and say ej contains a vertex with label {i, i + 1,..., i + m2/2 — 1}, subscripts mod m2. Then t'(P) is asymmetric and satisfies n2 = rm1 + 2m2_1. 77 Ars Math. Contemp. 10 (2016) 99-112 If kmi is even and m2 is odd, let t'(P) be a (0, k + 2, mi, ni)-asymmetric hypergraph, together with a degree 0 vertex of every nonempty label. Suppose that t'(P) has exactly the following m2 defects: for degree 2 vertices vi,..., vm2, v» is labeled [m2] - {i}. Then t(P) is asymmetric, and n2 = rmi + 2m2-i - 1. If kmi is odd and m2 is even, then let t'(P) be an (m2 +1, k + 2, mi, ni)-asymmetric hypergraph with ei,..., em2+i the edges that intersect k + 1 other edges, together with a degree 0 vertex of every nonempty label. Choose the labels of the vertices of t'(P) so that there are no defects, except that em2+i contains a degree 1 vertex with every label of size at least m2 - j, together with a vertex labeled 0. For 1 < i < m2, e» contains a degree 1 vertex labeled {i, i + 1,..., i + m2/2 - 1}, subscripts mod m2. Then t(P) is asymmetric and satisfies n2 = rmi + 2m2-i - 1/2. Finally, if kmi and m2 are both odd, then let t'(P) be an (m2, k + 2, mi, ni)-asym-metric hypergraph, together with a degree 0 vertex of every nonempty label. Choose the labels of t'(P) so that there are no defects, and if the edges with k + 1 degree 1 vertices are ei,..., em2, then e» contains a vertex labeled {i, i + 1,..., i + m2/2 - 1/2}, with subscripts mod m2. Then t(P) is asymmetric and satisfies n2 = rmi + 2m2-i - 1/2. References [1] M. Albertson, K. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 #R18 (1996), 17 pp. [2] R. Bailey, P. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society, 43 (2011), 209-242. [3] Bela Bollobas, Random Graphs, 2nd edition, Cambridge University Press (2001). Section 7.6. [4] F. Bergeron, G. Labelle, P. Leroux, Thorie des espces et combinatoire des structures arborescentes, LaCIM, Montreal 1994. English version: Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998. [5] D. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin., 13(1) #R78 (2006), 12 pp. [6] D. Boutin, Small Label Classes in 2-Distinguishing Labelings, Ars Math. Contemp., 1(2) (2008), 154-164. [7] M. Ellingham, J. Schroeder, Distinguishing partitions and asymmetric uniform hypergraphs, Ars Math. Contemp., 4(1) (2011), 111-123. [8] F. Harary, R. W. Robinson, A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 41 (1986), p. 325. [9] J. H. Kim, B. Sudakov, V. Vu, On the asymmetry of random regular graphs and random graphs, Random Structures Algorithms - Special issue: Proceedings ofthe tenth international conference "Random structures and algorithms", Volume 21 Issue 3-4, October 2002. [10] R. Otter. The Number of Trees, Ann. Math. 49 (1948), 583-599. [11] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11 #R63 (2004), 13 pp.