ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 311-318
https://doi.org/10.26493/1855-3974.1435.c71
(Also available at http://amc-journal.eu)
Vertex transitive graphs G with xd (G) > x(G) and small automorphism group*
Niranjan Balachandran
Department of Mathematics, Indian Institute of Technology Bombay, Mumbai, India
Sajith Padinhatteeri t
Department ofECE, Indian Institute ofScience, Bangalore, India
Pablo Spiga
Dipartimento Di Matematica E Applicazioni, University ofMilano-Bicocca, Milano, Italy Received 24 June 2017, accepted 1 October 2019, published online 29 October 2019
For a graph G and a positive integer k, a vertex labelling f: V (G) ^ {1,2,... ,k} is said to be k-distinguishing if no non-trivial automorphism of G preserves the sets f-1(i) for each i e {1,..., k}. The distinguishing chromatic number of a graph G, denoted Xd(G), is defined as the minimum k such that there is a k-distinguishing labelling of V(G) which is also a proper coloring of the vertices of G. In this paper, we prove the following theorem: Given k e N, there exists an infinite sequence of vertex-transitive graphs Gi = (Vi,Ei) such that
2. | Aut(Gj)| < 2k|Vj|, where Aut(Gj) denotes the full automorphism group of Gj.
In particular, this answers a question posed by the first and second authors of this paper.
Keywords: Distinguishing chromatic number, vertex transitive graphs, Cayley graphs. Math. Subj. Class.: 05C15, 05D40, 20B25, 05E18
*The first and second authors would like to thank Ted Dobson for useful discussions. t Supported by grant PDF/2017/002518, Science and Engineering Research Board, India. E-mail addresses: niranj@math.iitb.ac.in (Niranjan Balachandran), sajithp@iisc.ac.in (Sajith Padinhatteeri), pablo.spiga@unimib.it (Pablo Spiga)
Abstract
1. Xd(Gi) > x(Gi) > k,
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
312
Ars Math. Contemp. 17 (2019) 291-310
1 Introduction
Let G be a graph. An automorphism of G is a permutation ( of the vertex set V(G) of G such that, for any x, y G V(G), f (x), f (y) are adjacent if and only x, y are adjacent. The automorphism group of a graph G, denoted by Aut(G), is the group of all automorphisms of G. A graph G is said to be vertex transitive if, for any u, v G V(G), there exists ( G Aut(G) such that f (u) = v.
Given a positive integer r, an r-coloring of G is a map f: V(G) ^ {1, 2,..., r} and the sets f-1(i), for i g {1,2 ..., r}, are the color classes of f. An automorphism ( G Aut(G) is said to fix a color class C of f if f (C) = C, where f (C) = {((v) : v G C}. A coloring of G, with the property that no non-trivial automorphism of G fixes every color class, is called a distinguishing coloring of G.
Collins and Trenk in [5] introduced the notion of the distinguishing chromatic number of a graph G, which is defined as the minimum number of colors needed to color the vertices of G so that the coloring is both proper and distinguishing. Thus, the distinguishing chromatic number of G is the least integer r such that the vertex set can be partitioned into sets V1, V2,..., Vr such that each V is independent in G, and for every non-trivial ( G Aut(G) there exists some color class V with f (Vj) = Vj. The distinguishing chromatic number of a graph G, denoted by xd (G), has been the topic of considerable interest recently (see, for instance, [1, 2, 3, 4]).
One of the many questions of interest regarding the distinguishing chromatic number concerns the contrast between xd(G) and the cardinality of Aut(G). For instance, the Kneser graphs K(n, r) have very large automorphism groups and yet, xd (K(n, r)) = x(K(n, r)) for n > 2r +1, and r > 3 (see [2]). The converse question is compelling: Are there infinitely many graphs Gn with 'small' automorphism groups and satisfying Xd(G„) > X(G„)7
The question as posed above is not actually interesting for two reasons. First, for all even n, xd (Cn) > x(Cn) = 2 and | Aut(Cn)| = 2n, where Cn is the cycle of length n. Second, if one stipulates that G also has arbitrarily large chromatic number, then here is a construction for such a graph. Start with a rigid graph G with a leaf vertex x and having large chromatic number (one can obtain this by minor modifications to a random graph, for instance); then, blow up the leaf vertex x to a new disjoint set X whose neighborjn the new graph G is the same as the neighbor of x in G. In fact one can arrange for xd (G) - x(G) to be as large as one desires. Furthermore, since | Aut(G)| = |X |!, this provides examples of graphs for which the automorphism groups are relatively 'small' in terms of the order of the graph.
In the example above, the fact that xd(G) is larger than x(G) is accounted for by a 'local' reason, and that is what makes the problem stated above not very interesting. However, if one further stipulates that the graph is vertex-transitive, then the same question is highly non-trivial. In [1], the first and second authors constructed families of vertex-transitive graphs with xd(G) > x(G) > k and | Aut(G)| = O(|V(G)|3/2), for any given k. In this paper, we improve upon that result:
Theorem 1.1. Given k G N, there exists an infinite family of graphs Gn = (Vn,En) satisfying:
1.	XD (Gn) > x(Gn) > k,
2.	Gn is vertex transitive and | Aut(Gn)| < 2k|Vn|.
N. Balachandran et al.: Vertex transitive graphs G with \d (G) > x(G) and small... 313
Our family of graphs consists of Cayley graphs. To recall the definition, let A be a group and let S be an inverse-closed subset of A, i.e., S = S-1, where S-1 := {s-1 : s G S}. The Cayley graph Cay(A, S) is the graph with vertex set A and the vertices u and v are adjacent in Cay(A, S) if and only if uv-1 G S.
We start with a brief description of the graphs of our construction. For q, an odd prime, let F^ denote the n-dimensional vector space over Fq. Our graphs shall be Cayley graphs Cay(F^,S) for some suitable inverse-closed set S c F^ which is obtained by taking a union of a certain collection of lines in F^ and then deleting the zero element of F^. More precisely, let H0 := {(x1,x2,..., xn-1,0) : xj G Fq, 1 < i < n - 1} and let
0	denote the element (0,..., 0) g F£. For each line (1-dimensional subspace of F£)
1	c F^ satisfying I n H0 = {0}, pick I independently with probability 1/2 to form the random set S. Our connection set S for the Cayley graph Cay(F^, S) is defined by S := {v G F^ : v G I for some I G S} \ {0}. Our main theorem states that with high probability, Gn,S := Cay(F^, S) satisfies the conditions of Theorem 1.1.
To show that these graphs have 'small' automorphism groups, we prove a stronger version of Theorem 4.3 of [6] in this particular context, which is also a result of independent interest.
Theorem 1.2. Let q be a prime power, let n be a positive integer with n > 2 and let G be the additive group of the n-dimensional vector space F^ over the finite field Fq of cardinality q, and let F* := Fq \ {0} be the multiplicative group of the field Fq with its natural group action on G by scalar multiplication, and write K := F^ x F*. If S is an inverse-closed subset of G with K < Aut(Cay(G, S)), then either
(i)	Aut(Cay(G, S)) = K, or
(ii)	there exists f G Aut(Cay(G, S)) \ K with f normalizing G.
Remark 1.3. Theorem 1.2 is valid even though the connection set S is not inverse-closed. Since we deal with Cayley graphs the phrase inverse-closed subset is used in the statement of the theorem.
The rest of the paper is organized as follows. We start with some preliminaries in Section 2 and then include the proofs of Theorems 1.1 and 1.2 in the next section. We conclude with some remarks and some open questions.
2 Preliminaries
We begin with a few definitions from finite geometry. For more details, one may see [13, 14]. By PG(n, q) we mean the Desarguesian projective space obtained from the affine space AG(n + 1, q).
Definition 2.1. A cone with vertex A c PG(k, q) and base B c PG(n — k — 1, q), where PG(k, q) n PG(n — k — 1, q) = 0, is the set of points lying on the lines connecting points of A and B.
Definition 2.2. Let V be an (n + 1)-dimensional vector space over a finite field F. A subset S of PG(V) is called an Fq-linear set if there exists a subset U of V that forms an Fq-vector space, for some Fq c F, such that S = B(U), where
B(U) := |(u)f : u € U \ {0}}
314
Ars Math. Contemp. 17 (2019) 291-310
and where (u)F denotes the projective point of PG(V), corresponding to the vector u of
u c v .
Further details about Fq-linear sets can be found in [14], for instance. The projective space PG(n, q) can be partitioned into an affine space AG(n, q) and a hyperplane at infinity, denoted by
Definition 2.3. Following [13], we say that a set of points U c AG(n, q) determines the direction d e if there is an affine line through d meeting U in at least two points.
We now state the main theorem of [13] which will be relevant in our setting.
Theorem 2.4. Let U c AG(n, Fq), n > 3, |U| = qk. Suppose that U determines at most qk-1 + qk-2 + • • • + q2 + q directions and suppose that U is an Fp-linear set of points, where q = ph, p > 3 prime. If n — 1 > (n — k)h, then U is a cone with an (n — 1 — h(n — k))-dimensional vertex at and with base a Fq-linear point set U(„_fc)h of size q(n-k)(h-1), contained in some affine (n — k) h-dimensional subspace of AG(n, q).
We end this section by recalling another result that appears in [6] as Theorem 4.2.
Theorem 2.5. Let G be a permutation group on Q with a proper self-normalizing abelian regular subgroup. Then |Q| is not a prime power.
3 Proofs of the Theorems
In this section we prove Theorems 1.1 and 1.2 starting with the proof of Theorem 1.2. We believe that this result is only the tip of an iceberg: its current statement has been tailored to the context of our setting, and uses some ideas that appear in [6, Section 3] and [9].
Proof of Theorem 1.2. We suppose that (i) does not hold, that is, K is a proper subgroup of Aut(Cay(G, S)); we show that (ii) holds. Write r := Cay(G, S).
Let B be a subgroup of Aut(r) with K < B and with K maximal in B. Suppose that K < B. As G is characteristic in K, we get G < B. In particular, every element ^ in B \ K satisfies (ii).
Suppose then that K is not normal in B. Since K is maximal in B and G < K, we have NB (G) = K. Suppose that there exists b e B \ K such that L := (G, Gb) (the smallest subgroup of B containing G and Gb) satisfies L n K = G. We claim that we are now in the position to apply Theorem 2.5 (and implicitly some ideas from [9]). Indeed, as NL (G) = NB (G) n L = Kn L = G, L is a transitive permutation group on the vertices of r with a proper regular self-normalizing abelian subgroup G. (Observe that G is a proper subgroup of L because b e NB (G) = K.) By Theorem 2.5, |G| is not a prime power, which is a contradiction because |G| = qn. This proves that, for every b e B \ K, we have (G, Gb) n K > G.
Fix b e B \ K. Now, G and Gb are abelian and hence G n Gb is centralized by (G, Gb). From the preceding paragraph, there exists k e (G, Gb) n K with k e G. Observe now that K = F^ x F* is a Frobenius group with kernel G = F^ and complement F*. Therefore, k acts by conjugation fixed-point-freely on G \ {0}. As k centralizes G n Gb, we deduce
|G n Gb | = 1.
Let C := f|xeB Kx be the core of K in B. As G n Gb = 1 for all b e B \ K, K n Kb has no non-identity q-elements. Therefore C n G = 1. As C < B and C < K, C is
N. Balachandran et al.: Vertex transitive graphs G with \d (G) > x(G) and small... 
315
a normal subgroup of the Frobenius group K intersecting its kernel on the identity. This yields C = 1.
Let Q be the set of right cosets of K in B. From the paragraph above, B acts faithfully on Q. Moreover, as K is maximal in B, the action of B on Q is primitive. Therefore B is a finite primitive group with a solvable point stabilizer K. In [11], Li and Zhang have explicitly determined such primitive groups: these are classified in [11, Theorem 1.1] and [11, Tables I-VII]. Now, using the terminology in [11], a careful (but not very difficult) case-by-case analysis on the tables in [11] shows that B is a primitive group of affine type, that is, B contains an elementary abelian normal r-subgroup V, for some prime r. For this analysis it is important to keep in mind that the stabilizer K is a Frobenius group with kernel the elementary abelian group G = F^ and n > 2.
Let | V | = r4. Now, the action of B on Q is permutation equivalent to the natural action of B = V x K on V, with V acting via its regular representation and with K acting by conjugation. Observe that q = r, because K acts faithfully and irreducibly as a linear group on V and hence K contains no non-identity normal r-subgroups. Observe further that |B| = |V||K| = r4 • qn • (q - 1).
We are finally ready to reach a contradiction and to do so, we go back studying the action of B on the vertices of r. Observe that B is solvable because V is solvable and so is B/V = K. We write B0 for the stabilizer in B of the vertex 0 of r. As G acts regularly on the vertices of r, we obtain B = B0G and B0 n G = 1. In particular, |B01 = r4 • (q - 1). Observe that B0 is a Hall n-subgroup of the solvable group B, where n is the set of all the prime divisors of q - 1 together with the prime r. As V is a n-subgroup, from the theory of Hall subgroups (see for instance [7], Theorem 3.3), V has a conjugate contained in B0. Since V < B, we have V < B0. This is clearly a contradiction because V is normal in B, but B0 is core-free in B, being the stabilizer of a point in a transitive permutation group.	□
For the next lemma, recall that
Ho := {(xi, X2,..., xn_i, 0) : Xj € Fq, 1 < i < n — 1}.
In what follows, Gn,s will denote the Cayley graph Cay(F^, S) and S = S \ {0} for some set S = £, where L is a collection of lines in F^ with each £ € L satisfying £ n Ho = {0}.
Lemma 3.1. If L = 0, then x(Gn,S) = q.
Proof. Observe that each line that belongs to the set S gives rise to a clique of size q in the graph Gn,s. Therefore x(Gn,S) > q. On the other hand, for a fixed v € S, the partition (Ca)a£F,, where C\ := {w + Av : w € H0}, of the vertex set F^ is a proper coloring of the graph Gn S. Indeed, for any distinct x = w1 + Av, y = w2 + Av in Cx, we have x - y = w1 - w2 € S because w1 - w2 € H0 and S n H0 = 0. Therefore the sets C\ are independent in Gn,s for each A € Fq.	□
Lemma 3.2. Assume that q is prime. Let S be the random set corresponding to a union of lines £ in F^ with £ n H0 = {0} and where each £ € F^ is chosen independently with
probability ^; and let S = S \ {0}. Then
( qn_3
P (XD (Gn,s) > q) > 1 - exp -
316
Ars Math. Contemp. 17 (2019) 291-310
Proof. First, note that E(|S|) = , so taking 5 = 1 and ^ = E(|S|) in the Chernoff bound (see (2.6) on page 26 of [10]) we obtain
P (¡SKi-^) < exp (In particular, with probability at least 1 - exp(-qn-3/4), we have |S| > q-——. We
n — 1_ n — 2
may thus assume |S| > q--1— in what follows.
We claim that every color class in a proper q-coloring of Gn,S is an affine hyperplane of Fn. To see why, let Ci,..., Cq be independent sets in Gn,S witnessing a proper q-coloring of Gn,S. Fix v G S and consider the line tv := {Av : A G Fq} along with its translates tv + w := {Av + w : A G Fq}, for w G H0. Each set tv + w is a clique of size q in Gn,S, and these cliques partition the vertex set of Gn,S, so in particular each C contains at most one vertex from each of these translates tv + w. Consequently, |Cj | < qn-i for all i G {1,..., q}. By size considerations, it follows that | Cj | = qn-1 for each i G {1,..., q}.
Consider a color class C. Suppose C determines at least ^r3 qn-2 + qn-3 + • • • + q2 + q +1 directions. Then if (C} denotes the set of all vertices in the affine lines intersecting
at least two points in C, we have |(C}| + |S| > 1 + q +----+ qn-1, so (C} n S = 0.
However, this contradicts the assumption that C is an independent set in Gn,S. Therefore C determines at most ^j3qn-2 + qn-3 + • • • + q2 + q directions. Since q is prime, by Corollary 10 in [13], it follows that C is an Fq-linear set. Hence, by Theorem 2.4, the color class C is a cone with an n - 2 (projective) dimensional vertex V at and an affine point u1 as base. In particular, the affine plane corresponding to the Fq-subspace spanned by V passing through the affine point u1 is contained in C. Since |C| = qn-i, it follows that C is this affine hyperplane, and this proves the claim.
To complete the proof, observe that for each A g Fq\{1},themap yx(x) = Ax, x G Fq fixes each color class. Moreover, yx fixes the set S and yx (u) - y x (v) = yx (u - v), so ya is a non-trivial automorphism which fixes each color class. Therefore xd (Gn,s) > q. D
Lemma 3.3. If n > 6 and q > 5 is prime, then Aut(G„jS) = Fq x Fq with probability at least
q"—1 1 - 2--^.
Proof. Since Gn,S is a Cayley graph on the additive group G = Fq, by Theorem 1.2, either Aut(Gn,S) = K = Fq x Fq or there exists y G Aut(Gn,S) \ K with y normalizing
'	q"—1 '
G = Fq. We show that with probability at least 1 - 2 3 , there is no y satisfying the latter condition.
Suppose y G Aut(Gn,S) normalizes Fq. If a = y(0) and An : Fq ^ Fq is the right translation via a, then A-1 y is an automorphism of Gn S normalizing Fq and with (A-1y)(0) = (A-1)(y(0)) = (A-1)(a) = a - a = 0. Therefore, without loss of generality, we may assume that y(0) = 0. Since S is the neighbourhood of 0 in Gn S, we get y(S) = S. Moreover, since y acts as a group automorphism on Fq, we have y G GLn(q).
Now, for y G GLn(q), let denote the event y(S) = S. Let L denote the set of all lines t with t n H0 = 0. Also, let Orbv(t) = {t, y(t), y2(t),..., yk(t)} where yfc+1(t) = t. Then
P(EV) < H21-|Orb^(£i)| =2n^-|l|, i=1
N. Balachandran et al.: Vertex transitive graphs G with \d (G) > x(G) and small... 
317
where N, denotes the number of distinct orbits of p in L. Setting G = GL(n, q) \ {AI :
A g F*}, we have
P (U E, ) < E P(E^) < 2-|L|E 2Nv .	(3.1)
Let F, := { g L : p(^) = ¿}| and F := maxve5 F, Now N, < F + J^—^ = ^+2^. Thus, it suffices to give a suitable upper bound for F. Towards that end, we note that, if F, = F for p g G, then every line I fixed by p corresponds to an eigenvector of ¡p. If Ei, E2,..., Ek denote the eigenspaces of p for some distinct eigenvalues Ai,..., Ak, then
F, < E ((dimEi) - (dim(E;nHo))) < q-2 + 1.
Similarly, we have |L| = - (n-1)a = qn-i, and so by (3.1), we have
III	1	F-|L|	2	qn 1 — qn 2 — 1	qn 1
P ( U E, ) < |G|2^ < qn 2--2- < 2--3-,
for q > 5, n > 6.	□
Computations and estimates similar to the ones presented in the proof of Lemma 3.3 have been proved useful in a variety of problems, see for instance [1, 8] and [12, Section 6.4].
Proof of Theorem 1.1. Given k g N with k > 4, pick a prime number q with k < q < 2k. For n > 6, consider the random graph Gn,S of the group Fn as constructed above. By Lemmas 3.1, 3.2 and 3.3, with positive probability, the graph Gn S satisfies the statements of the lemmas, and hence satisfies the conclusions of Theorem 1.1.	□
4 Concluding remarks
• We observe that, for S chosen randomly as in the proof of our result, the distinguishing chromatic number of Gn,S is q +1 with high probability. Indeed, consider the q-coloring C described in Lemma 3.1. Re-color the vertex 0 using an additional color. Then the coloring described by the partition C = C U {0} is a proper, distinguishing coloring of Gn,S with q +1 colors. In fact, C' is clearly proper, and to show that it is distinguishing, consider p g Aut(Gn,S) = Fn x F* (by Lemma 3.3) that fixes every color class. Write p(x) = Ax + b with A g F*, b g F^ Since p fixes the color class containing 0, we have b = 0. Also, x and Ax cannot be in same color class unless A = 1. Therefore p is the identity automorphism.
It is interesting to determine if one can obtain families of vertex-transitive graphs with xd (G) > x(G) + 1, with 'small' automorphism groups and with x(G) being arbitrarily large. In fact, for k g N, there is no known family of vertex-transitive graphs for which xd(g) > x(G) + 1 > k and | Aut(G)| = O(|V(G)|O(1)). It is plausible that Cayley graphs over certain groups may provide the correct constructions.
318
Ars Math. Contemp. 17 (2019) 291-310
• Theorem 1.1 establishes, for any fixed k, the existence of vertex-transitive graphs
Gn = (Vn,En) with xd(Gn) > x(Gn) > k and with | Aut(Gn)| < 2k|Vn|. It would be interesting to obtain a similar family of graphs that satisfy with xd (Gn) > x(Gn) > k and with | Aut(Gn)| < C|Vn |, for some absolute constant C.
References
[1]	N. Balachandran and S. Padinhatteeri, xd (G), |Aut(G)| and a variant of the Motion Lemma, ArsMath. Contemp. 12 (2017), 89-109, doi:10.26493/1855-3974.848.669.
[2]	Z. Che and K. L. Collins, The distinguishing chromatic number of Kneser graphs, Electron. J. Combin. 20 (2013), #P23 (12 pages), https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v2 0i1p2 3.
[3]	J. O. Choi, S. G. Hartke and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, SIAM J. Discrete Math. 24 (2010), 82-100, doi:10.1137/060651392.
[4]	K. L. Collins, M. Hovey and A. N. Trenk, Bounds on the distinguishing chromatic number, Electron. J. Combin. 16 (2009), #R88 (14pages), https://www.combinatorics.org/ ojs/index.php/eljc/article/view/v16i1r88.
[5]	K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16 (19 pages), https://www.combinatorics.org/ojs/index.php/ eljc/article/view/v13i1r16.
[6]	E. Dobson, P. Spiga and G. Verret, Cayley graphs on abelian groups, Combinatorica 36 (2016), 371-393, doi:10.1007/s00493-015-3136-5.
[7]	K. Doerk and T. O. Hawkes, Finite Soluble Groups, volume 4 of De Gruyter Expositions in Mathematics, De Gruyter, Berlin, 1992, doi:10.1515/9783110870138.
[8]	S. Guest and P. Spiga, Finite primitive groups and regular orbits of group elements, Trans. Amer. Math Soc. 369 (2017), 997-1024, doi:10.1090/tran6678.
[9]	E. Jabara and P. Spiga, Abelian Carter subgroups in finite permutation groups, Arch. Math. (Basel) 101 (2013), 301-307, doi:10.1007/s00013-013-0558-4.
[10]	S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 2000, doi:10.1002/ 9781118032718.
[11]	C. H. Li and H. Zhang, The finite primitive groups with soluble stabilizers, and the edge-primitive s-arc transitive graphs, Proc. Lond. Math. Soc. 103 (2011), 441-472, doi:10.1112/ plms/pdr004.
[12]	P. Potocnik, P. Spiga and G. Verret, Asymptotic enumeration of vertex-transitive graphs of fixed valency, J. Comb. Theory Ser. B 122 (2017), 221-240, doi:10.1016/j.jctb.2016.06.002.
[13]	L. Strome and P. Sziklai, Linear point sets and Redei type k-blocking sets PG(n, q), J. Algebraic Combin. 14 (2001), 221-228, doi:10.1023/a:1012724219499.
[14]	G. V. Voorde, Blocking Sets in Finite Projective Spaces and Coding Theory, Ph.D. thesis, Ghent University, Belgium, 2010.