On sensitivity in bipartite Cayley graphs. (English) Zbl 1483.05078
Summary: H. Huang [Ann. Math. (2) 190, No. 3, 949–955 (2019; Zbl 1427.05116)] proved that every set of more than half the vertices of the \(d\)-dimensional hypercube \(Q_d\) induces a subgraph of maximum degree at least \(\sqrt{ d}\), which is tight by a result of F. R. K. Chung et al. [J. Comb. Theory, Ser. A 49, No. 1, 180–187 (1988; Zbl 0653.05037)]. Huang [loc. cit.] asked whether similar results can be obtained for other highly symmetric graphs.
First, we present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree 1 on more than half the vertices. In particular, this refutes a conjecture of A. Potechin and H. Y. Tsang [“A conjecture on induced subgraphs of Cayley graphs”, Preprint, arXiv:2003.13166], for which first counterexamples were shown recently by F. Lehner and G. Verret [Ars Math. Contemp. 19, No. 1, 77–82 (2020; Zbl 1465.05195)]. The first family consists of dihedrants and contains a sporadic counterexample encountered earlier by Lehner and Verret [loc. cit.]. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are \(d\)-regular containing an induced matching on a \(\frac{ d}{ 2 d - 1} \)-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret [loc. cit.]. Second, we consider Huang’s lower bound for graphs with subcubes and show that the corresponding lower bound is tight for products of Coxeter groups of type \(\mathcal{A}_n\), \(\mathcal{I}_2(2 k + 1)\), and most exceptional cases. We believe that Coxeter groups are a suitable generalization of the hypercube with respect to Huang’s question.
Finally, we show that induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This gives classes of Cayley graphs with properties similar to the ones provided by Huang’s results. However, in contrast to Coxeter groups these graphs have no subcubes.
First, we present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree 1 on more than half the vertices. In particular, this refutes a conjecture of A. Potechin and H. Y. Tsang [“A conjecture on induced subgraphs of Cayley graphs”, Preprint, arXiv:2003.13166], for which first counterexamples were shown recently by F. Lehner and G. Verret [Ars Math. Contemp. 19, No. 1, 77–82 (2020; Zbl 1465.05195)]. The first family consists of dihedrants and contains a sporadic counterexample encountered earlier by Lehner and Verret [loc. cit.]. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are \(d\)-regular containing an induced matching on a \(\frac{ d}{ 2 d - 1} \)-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret [loc. cit.]. Second, we consider Huang’s lower bound for graphs with subcubes and show that the corresponding lower bound is tight for products of Coxeter groups of type \(\mathcal{A}_n\), \(\mathcal{I}_2(2 k + 1)\), and most exceptional cases. We believe that Coxeter groups are a suitable generalization of the hypercube with respect to Huang’s question.
Finally, we show that induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This gives classes of Cayley graphs with properties similar to the ones provided by Huang’s results. However, in contrast to Coxeter groups these graphs have no subcubes.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C99 | Graph theory |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Akers, S. B.; Harel, D.; Krishnamurthy, B., The Star Graph: An Attractive Alternative to the n-Cube, 145-152 (1994), IEEE Computer Society Press: IEEE Computer Society Press Washington, DC, USA |
| [2] | Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 555-566 (1989) · Zbl 0678.94026 |
| [3] | Alon, N.; Chung, F. R.K., Explicit construction of linear sized tolerant networks, Discrete Math., 72, 15-19 (1988) · Zbl 0657.05068 |
| [4] | Alon, N.; Roichman, Y., Random Cayley graphs and expanders, Random Struct. Algorithms, 5, 271-284 (1994) · Zbl 0798.05048 |
| [5] | Alon, N.; Spencer, J. H., The Probabilistic Method (2016), John Wiley & Sons: John Wiley & Sons Hoboken, NJ · Zbl 1333.05001 |
| [6] | Alon, N.; Zheng, K., Unitary signings and induced subgraphs of Cayley graphs of \(\mathbb{Z}_2^n (2020)\) · Zbl 1455.05022 |
| [7] | Bishnoi, A.; Mattheus, S.; Schillewaert, J., Minimal multiple blocking sets, Electron. J. Comb., 25, Article P4.66 pp. (2018) · Zbl 1410.51009 |
| [8] | Björner, A., Orderings of Coxeter groups, (Combinatorics and Algebra, Proc. Conf.. Combinatorics and Algebra, Proc. Conf., Boulder/Colo., 1983. Combinatorics and Algebra, Proc. Conf.. Combinatorics and Algebra, Proc. Conf., Boulder/Colo., 1983, Contemp. Math., vol. 34 (1984)), 175-195 · Zbl 0594.20029 |
| [9] | Björner, A.; Brenti, F., Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231 (2005), Springer: Springer New York · Zbl 1110.05001 |
| [10] | Björner, A.; Edelman, P. H.; Ziegler, G. M., Hyperplane arrangements with a lattice of regions, Discrete Comput. Geom., 5, 263-288 (1990) · Zbl 0698.51010 |
| [11] | Brinkmann, G.; Coolsaet, K.; Goedgebeur, J.; Mélot, H., House of graphs: a database of interesting graphs, Discrete Appl. Math., 161, 311-314 (2013) · Zbl 1292.05254 |
| [12] | Chung, F. R.K.; Füredi, Z.; Graham, R. L.; Seymour, P., On induced subgraphs of the cube, J. Comb. Theory, Ser. A, 49, 180-187 (1988) · Zbl 0653.05037 |
| [13] | Coxeter, H. S.M., The complete enumeration of finite groups of the form \(R_i^2 = ( R_i R_j )^{k_{i j}} = 1\), J. Lond. Math. Soc., s1-10, 21-25 (1935) · Zbl 0010.34202 |
| [14] | Cplex I.I., V12. 1: user’s manual for CPLEX, vol. 46, International Business Machines Corporation, 2009, p. 157. |
| [15] | Eppstein, D., Cubic partial cubes from simplicial arrangements, Electron. J. Comb., 13, Article R79 pp. (2006) · Zbl 1115.05080 |
| [16] | Eppstein, D., The many faces of the Nauru graph (2007) |
| [17] | Felsner, S.; Hochstättler, W.; Knauer, K.; Steiner, R., Complete acyclic colorings, Electron. J. Comb., 27, Article P2.40 pp. (2020) · Zbl 1441.05073 |
| [18] | Gamburd, A.; Hoory, S.; Shahshahani, M.; Shalev, A.; Virág, B., On the girth of random Cayley graphs, Random Struct. Algorithms, 35, 100-117 (2009) · Zbl 1230.05156 |
| [19] | The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.11.0, 2020. |
| [20] | Gyárfás, A., Problems from the world surrounding perfect graphs, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041 |
| [21] | Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226/228, 593-616 (1995) · Zbl 0831.05044 |
| [22] | Holt, D.; Royle, G., A census of small transitive groups and vertex-transitive graphs, J. Symb. Comput., 101, 51-60 (2020) · Zbl 1528.20004 |
| [23] | Huang, H., Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann. Math. (2), 190, 949-955 (2019) · Zbl 1427.05116 |
| [24] | Las Vergnas, M., Convexity in oriented matroids, J. Comb. Theory, Ser. B, 29, 231-243 (1980) · Zbl 0443.05026 |
| [25] | Lehner, F.; Verret, G., Counterexamples to “A conjecture on induced subgraphs of Cayley graphs” (2020) · Zbl 1465.05195 |
| [26] | Loz, E.; Mačaj, M.; Miller, M.; Šiagiová, J.; Širáň, J.; Tomanová, J., Small vertex-transitive and Cayley graphs of girth six and given degree: an algebraic approach, J. Graph Theory, 68, 265-284 (2011) · Zbl 1234.05121 |
| [27] | Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277 (1988) · Zbl 0661.05035 |
| [28] | Marušič, D.; Pisanski, T., The remarkable generalized Petersen graph \(G(8, 3)\), Math. Slovaca, 50, 117-121 (2000) · Zbl 0984.05044 |
| [29] | Morris, J.; Smolcic, J., Two families of graphs that are Cayley on nonisomorphic groups (2020) · Zbl 1465.05079 |
| [30] | Nisan, N.; Szegedy, M., On the degree of Boolean functions as real polynomials, Comput. Complex., 4, 301-313 (1994) · Zbl 0829.68047 |
| [31] | Potechin, A.; Tsang, H. Y., A conjecture on induced subgraphs of Cayley graphs (2020) |
| [32] | Potočnik, P.; Spiga, P.; Verret, G., Cubic vertex-transitive graphs on up to 1280 vertices, J. Symb. Comput., 50, 465-477 (2013) · Zbl 1256.05102 |
| [33] | Potočnik, P.; Spiga, P.; Verret, G., Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, J. Comb. Theory, Ser. B, 111, 148-180 (2015) · Zbl 1307.05114 |
| [34] | Royle, G.; Holt, D., Vertex-transitive graphs on fewer than 48 vertices (Sept. 2020) |
| [35] | Sloane, N. J.A.; Plouffe, S., The Encyclopedia of Integer Sequences (1995), Academic Press, Inc.: Academic Press, Inc. San Diego, CA · Zbl 0845.11001 |
| [36] | Stein, W., Sage mathematics software (version 9.0) (2020), The Sage Development Team |
| [37] | Tait, M.; Timmons, C., Independent sets in polarity graphs, SIAM J. Discrete Math., 30, 2115-2129 (2016) · Zbl 1350.05127 |
| [38] | Wilson, R. A., The Finite Simple Groups, Graduate Texts in Mathematics, vol. 251 (2009), Springer-Verlag London, Ltd.: Springer-Verlag London, Ltd. London · Zbl 1203.20012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
