¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 77-82
https://doi.org/10.26493/1855-3974.2301.63f
(Also available at http://amc-journal.eu)
Counterexamples to "A conjecture on induced subgraphs of Cayley graphs"*
Florian Lehner t ©
Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
Gabriel Verret * ©
Department of Mathematics, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Received 3 April 2020, accepted 28 May 2020, published online 7 November 2020
Abstract
Recently, Huang gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: every induced subgraph on a set of more than half the vertices has maximum degree at least %/d, where d is the valency of the hypercube. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian 2-group has the same property. Very recently, Potechin and Tsang proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We disprove this conjecture by constructing various counterexamples, including an infinite family of Cayley graphs of unbounded valency which admit an induced subgraph of maximum valency 1 on a set of more than half the vertices.
Keywords: Cayley graphs, vertex-transitive graphs, sensitivity conjecture. Math. Subj. Class. (2020): 05E18
1 Introduction
All graphs and groups in this paper are finite. Recently, Huang [5] gave a very elegant proof of the Sensitivity Conjecture [6] by proving that hypercube graphs have the following
*The authors would like to thank the anonymous referees for a number of helpful suggestions. tSupported by the Austrian Science Fund (FWF), grants J 3850-N32 and P 31889-N35.
* Supported by the N.Z. Marsden Fund, grant UOA1824.
E-mail addresses: mail@florian-lehner.net (Florian Lehner), g.verret@auckland.ac.nz (Gabriel Verret)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
78
Ars Math. Contemp. 19 (2020) 125-145
property: every induced subgraph on a set of more than half the vertices has maximum degree at least %/d, where d is the valency of the hypercube. This is best possible, as shown by Chung, Furedi, Graham and Seymour [2]. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian 2-group has the same property [1]. In their concluding remarks, they point out that this result cannot generalise directly to other groups, but that it would be interesting to investigate possible analogs for Cayley graphs on other groups.
Very recently, Potechin and Tsang proved such an analogous result for Cayley graphs on all abelian groups [7], by replacing the %/d bound by \Jd/2. (More precisely, they prove their result with the bound y x + x'/2, where x is the number of involutions in the connection set of the Cayley graph, and xX the number of non-involutions.) They also conjectured that their result should hold for all Cayley graphs [7, Conjecture 1] and asked whether even all vertex-transitive graphs might have this property.
In this short note, we give three infinite families of vertex-transitive graph such that every graph in these families admits an induced subgraph of maximum valency 1 on a set of more than half the vertices. First is the well-known family of odd graphs. Note that this family has unbounded valency and so these graphs fail to have the required property in a very strong sense. On the other hand, they are not Cayley. The second family consists of some 3-regular Cayley graphs on dihedral groups. The last family consists of an infinite family of graphs of unbounded valency which are Cayley on groups defined via iterated wreath products. Both the latter families are thus counterexamples to [7, Conjecture 1]. (We also note that, in our first two families, the induced subgraph in question is a matching, that is, each vertex has valency 1.)
2	Odd graphs
For n > 1, the odd graph On has vertex-set the n-subsets of a (2n + 1)-set Q, with two vertices adjacent if and only if the corresponding subsets are disjoint. For example Oi = K3, while O2 is isomorphic to the Petersen graph. Note that there is an obvious action of S2n+1 as a vertex-transitive group of automorphism of On, so these graphs are vertex-transitive. On the other hand, these graphs are not Cayley graphs for n > 2 [4]. It is easy to check that On is (n + 1)-regular. Let w G Q and let U be the set of n-subsets of Q that do not contain w. Note that
|U| = _£)_ = n±L > 1
|V(On)| (2nn+1) 2n ±1 2' but the induced subgraph on U is 1-regular.
3	3-valent Cayley graphs on dihedral groups
For a group G and an inverse-closed and identity-free subset S of G, the Cayley graph Cay(G, S) is the graph with vertex-set G and two vertices g and h adjacent if and only
g-1h G S. For n > 1, we denote by D2n the dihedral group (a, b | an = b2 = (ab)2 = 1} of order 2n.
Let r18 = Cay(D18, {b, ab, a3b}). There is a set U18 of 10 vertices of r18 such that the induced subgraph on U18 is 1-regular, as can be seen on the picture below, where the elements of U18 are coloured gray.
F. Lehner and G. Verret: Counterexamples to "A conjecture on induced subgraphs
79
Starting from Tig, it is easy to get an infinite family of further examples using covers: for m > 1, let r18m = Cay(D18m, {b,ab,a3b}) and let N be the subgroup of D18m generated by a9. Note that N is a normal subgroup of D18m of order m and D18m/N = D18. Let (: D18m ^ D18 be the natural projection and let U18m be the preimage of U18. Now, |U18m| = 10m and, since r18m is a (normal) cover of r18, the induced subgraph on U18m is 1-regular.
4 Cayley graphs on iterated wreath products
Let Z2 = {0,1} denote the cyclic group of order 2, let G be a group with identity element 1G and let (Z2)G denote the set of functions from G to Z2. Note that (Z2)G forms a group under pointwise addition. Let 0 be the identity element of (Z2)G (that is, the function mapping every element of G to 0). Note also that there is natural action of G on (Z2)G. Written in exponential notation, we have that if a G (Z2)G and g G G, then ag is the element of (Z2)G defined by ag(x) = a(g-1x) for every x G G.
The wreath product Z21 G is the group consisting of all pairs (a, g) where a G (Z2)G and g G G, with the group operation given by
(a,g)(b, h) = (a + bg,gh).
For g G G, let ag G (Z2)G be the function mapping g to 1 and every other element of G to 0. If S is a generating set for G, then
{(a1, 1g)}U{(0,s) | s G S}
is a generating set for Z2 I G which we call the canonical generating set for Z2 I G (with respect to S).
80
Ars Math. Contemp. 19 (2020) 125-145
Example 4.1. Let G = Z2 = {0,1}, let S = {1} C G, let G = Z2 I G and let a = (a0,0), c = (0,1) € G. The canonical generating set for G with respect to S is S = {a, c}. Writing b = ac = (a0,0), Cay(G, S) is illustrated in Figure 2. (The colours of the vertices will be explained in Example 4.3.)
Figure 2: Cay(Z21 Z2, {a, c}).
Lemma 4.2. Let S be a generating set for a group G, let G = Z2 I G and let S be the canonical generating set for G with respect to S. If Cay(G, S) is bipartite and has an induced subgraph of maximum degree 1 on more than half the vertices, then the same is true for Cay(G, S).
Proof. We first show that Cay(G, S) is bipartite. Call an element of G even if it lies in the same part of the bipartition of Cay(G, S) as 1G, and odd otherwise. Call an element a of (Z2)g even if a maps an even number of elements of G to 1, and call a odd otherwise. Finally, call an element S = (a, g) € G even if a and g are either both even or both odd, and call S odd otherwise. It is straightforward to check that if S € S, then S is even if and only if gSS is odd. Thus the partition of GS into even and odd elements is a bipartition of Cay(G, S).
Let H C G be such that |H| > |G|/2 and the subgraph of Cay(G, S) induced by H has maximum degree 1. Denote by Geven and Godd the set of even and odd elements of G, respectively. For each a € (Z2)G, let [a] = {(a, g) | g € G} C G and define a subset Ha
F. Lehner and G. Verret: Counterexamples to "A conjecture on induced subgraphs ..." 81
of G as follows:
H if a = 0,
Godd if a = ag for some g G Ge , Geven otherwise.
Let H = {(a, h) | a G (Z2)G,h G Ha} C G. Clearly, |Hn [0]| = |H| > |G|/2 while, for a = 0, we have |H n [a]| = |G|/2. It follows that |H| > |G|/2. Let (a, h) G H. We show that (a, h) has at most one neighbour in H. By definition, h G Ha.
If a — 0, then h G H. Note that, if g G Geven, then Hag — Godd, whereas if g G Godd, then Hag = Geven. In particular, for every g G G, (ag, g) G Hi. It follows that (0, h)(ai, 1G) = (ah, h) = (ah, h) G Hi. On the other hand, for s G S, (0, h)(0, s) = (0, hs) G H if and only if hs G H. This shows that the number of neighbours of (0, h) in H is the same as the number of neighbours of h in H and therefore at most 1 (with equality reached for some h G H).
Assume now a = 0. Since the partition of G into even and odd elements is a bipartition of Cay(G, S), it follows from the definition of Ha that there are no two adjacent elements in H n [a]. Since (a, h) has exactly one neighbour outside of [a] (namely (a, h)(a1,1G)), it follows that (a, h) has at most one neighbour in H. This concludes the proof that the subgraph induced by H has maximum degree 1.	□
By starting with, say (G, S) = (Z2, {1}) and applying Lemma 4.2 repeatedly, one obtains an infinite family of Cayley graphs of unbounded valency such that every graph in the family admits an induced subgraph of maximum degree 1 on a set of more than half the vertices, as claimed.
Example 4.3. To illustrate Lemma 4.2, we pick off where Example 4.1 left off. We have Geven = {0} and Godd = {1}. Let H = G. Following Lemma 4.2, we have
Ho = {0,1}, Ha„ = {1}, Hai = {0},
Ha„+ai = {0}.
This gives H = {1, c, ac, b, abc}, which is the set of vertices coloured in gray in Figure 2. One can observe that this is more than half the vertices of the graph and that the induced subgraph on H has maximum valency 1.
5 Concluding remarks
1. Recall that a covering map f from a graph r to a graph r is a surjective map that is a local isomorphism. If such a map exists, then r is a covering graph of r. It is easy to see that if r is a d-regular graph admitting an induced subgraph of maximum degree 1 on a set of more than half the vertices, then r has the same property. (It is well known that all the vertex-fibers have the same cardinality, so one can simply take the preimage of the set of more than half the vertices of r.) Starting from one example, one can thus construct infinitely many having the same valency, vertex-transitivity, Cayleyness, etc.
82
Ars Math. Contemp. 19 (2020) 125-145
2.	As a consequence of the above remark, we can construct infinite families of d-regular Cayley graphs of order n admitting induced subgraphs of maximum degree 1 on
2 n vertices.
3.	It is an easy exercise that if r is a d-regular graph of order n admitting a subset X of vertices such that the induced graph on X has maximum valency at most 1, then |X|/n < ^¿i. Note that the Odd graph Od-1 attains this bound and so is extremal from this perspective. It would be interesting to know if this bound can be achieved by Cayley graphs. (Such examples were later found by Garcia-Marco and Knauer [3].)
4.	In light of the results from [1,7] on Cayley graphs of abelian groups, it seems natural ask if there is a natural family of nonabelian groups having the same property. In Sections 3 and 4, we give examples of Cayley graphs on some dihedral groups and some 2-groups that do not have this property. Given that both these families of groups are in some sense close to being abelian (dihedral groups have a cyclic subgroup of index 2, while 2-groups are nilpotent), the question of determining whether any natural family of nonabelian groups has this property seems even more interesting.
ORCID iDs
Florian Lehner © https://orcid.org/0000-0002-0599-2390 Gabriel Verret © https://orcid.org/0000-0003-1766-4834
References
[1]	N. Alon and K. Zheng, Unitary signings and induced subgraphs of Cayley graphs of Z£,
arXiv:2003.04926 [math.CO].
[2]	F. R. K. Chung, Z. Furedi, R. L. Graham and P. Seymour, On induced subgraphs of the cube, J. Comb. Theory Ser. A 49 (1988), 180-187, doi:10.1016/0097-3165(88)90034-9.
[3]	I. Garcia-Marco and K. Knauer, On sensitivity in bipartite Cayley graphs, arXiv:2009.00554 [math.CO].
[4]	C. D. Godsil, More odd graph theory, Discrete Math. 32 (1980), 205-207, doi:10.1016/ 0012-365x(80)90055-2.
[5]	H. Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann. of Math. 190 (2019), 949-955, doi:10.4007/annals.2019.190.3.6.
[6]	N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complex. 4 (1994), 301-313, doi:10.1007/bf01263419.
[7]	A. Potechin and H. Y. Tsang, A conjecture on induced subgraphs of Cayley graphs, arXiv:2003.13166 [math.CO].