Approximately strongly regular graphs. (English) Zbl 1508.05174
Summary: We give variants of the Krein bound, the absolute bound and the inertia bound for graphs with a spectrum similar to that of a strongly regular graph. In particular, we investigate what we call approximately strongly regular graphs. We apply our results to extremal problems. Among other things, we show the following:
(1) Caps in \(\mathrm{PG}(n, q)\) for which the number of secants on exterior points does not vary too much, have size \(O( q^{\frac{ 3}{ 4} n})\) (as \(q \to \infty\) or as \(n \to \infty \)).
(2) Optimally pseudorandom \(K_m\)-free graphs of order \(v\) and degree \(k\) for which the induced subgraph on the common neighborhood of a clique of size \(i \leq m - 3\) is similar to a strongly regular graph, have \(k = O( v^{1 - \frac{ 1}{ 3 m - 2 i - 5}})\).
(1) Caps in \(\mathrm{PG}(n, q)\) for which the number of secants on exterior points does not vary too much, have size \(O( q^{\frac{ 3}{ 4} n})\) (as \(q \to \infty\) or as \(n \to \infty \)).
(2) Optimally pseudorandom \(K_m\)-free graphs of order \(v\) and degree \(k\) for which the induced subgraph on the common neighborhood of a clique of size \(i \leq m - 3\) is similar to a strongly regular graph, have \(k = O( v^{1 - \frac{ 1}{ 3 m - 2 i - 5}})\).
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C35 | Extremal problems in graph theory |
| 51E22 | Linear codes and caps in Galois spaces |
| 05B05 | Combinatorial aspects of block designs |
Keywords:
strongly regular graphs; caps; clique-free graphs; Krein conditions; inertia bound; absolute boundReferences:
| [1] | Ajtai, M.; Komlós, J.; Szemerédi, E., A note on Ramsey numbers, J. Comb. Theory, Ser. A, 29, 3, 354-360 (1980) · Zbl 0455.05045 |
| [2] | Alon, N., Explicit Ramsey graphs and orthonormal labelings, Electron. J. Comb., 1, Article #R12 pp. (1994) · Zbl 0814.05056 |
| [3] | Alon, N.; Krivelevich, M., Constructive bounds for a Ramsey-type problem, Graphs Comb., 13, 3, 217-225 (1997) · Zbl 0890.05050 |
| [4] | Bishnoi, A.; Ihringer, F.; Pepe, V., A construction of clique-free pseudorandom graphs, Combinatorica, 40, 3, 307-314 (2020) · Zbl 1463.05373 |
| [5] | Bohman, T.; Keevash, P., The early evolution of the H-free process, Invent. Math., 181, 291-336 (2010) · Zbl 1223.05270 |
| [6] | Bollobás, B., Random Graphs (2001), Cambridge University Press · Zbl 0997.05049 |
| [7] | Bollobás, B.; Thomason, A., Graphs which contain all small graphs, Eur. J. Comb., 2, 13-15 (1981) · Zbl 0471.05037 |
| [8] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Heidelberg · Zbl 0747.05073 |
| [9] | Brouwer, A. E.; Van Maldeghem, H., Strongly Regular Graphs, Encyclopedia of Mathematics and Its Applications, vol. 182 (2022), Cambridge University Press · Zbl 1498.05001 |
| [10] | Bryant, D.; Catháin, P. Ó., An asymptotic existence result on compressed sensing matrices, Linear Algebra Appl., 475, 134-150 (2015) · Zbl 1312.05021 |
| [11] | Dalfó, C.; Fiol, M. A.; Garriga, E., On k-walk-regular graphs, Electron. J. Comb., 16 (2009), #R47 · Zbl 1226.05107 |
| [12] | Delsarte, Ph.; Goethals, J. M.; Seidel, J. J., Spherical codes and designs, Geom. Dedic., 6, 363-388 (1977) · Zbl 0376.05015 |
| [13] | Edel, Y., Extensions of generalized product caps, Des. Codes Cryptogr., 31, 1, 5-14 (2004) · Zbl 1057.51005 |
| [14] | Edel, Y.; Bierbrauer, J., Recursive constructions for large caps, Bull. Belg. Math. Soc., 6, 249-258 (1999) · Zbl 0941.51009 |
| [15] | Edel, Y.; Bierbrauer, J., Large caps in small spaces, Des. Codes Cryptogr., 23, 197-212 (2001) · Zbl 0994.51005 |
| [16] | Ellenberg, J. S.; Gijswijt, D., On large subsets of \(\mathbb{F}_q^n\) with no three-term progression, Ann. Math., 185, 339-343 (2017) · Zbl 1425.11020 |
| [17] | Elsholtz, C.; Lipnik, G. F., Exponentially larger affine and projective caps (2022) |
| [18] | Glock, S.; Janzer, O.; Sudakov, B., New results for MaxCut in H-free graphs (2021) |
| [19] | Goldberg, F., On quasi-strongly regular graphs, Linear Multilinear Algebra, 54, 6, 437-451 (2006) · Zbl 1108.05097 |
| [20] | Goryainov, S.; Shalaginov, L. V., Deza graphs: a survey and new results (2021) |
| [21] | Greaves, G.; Syatriadi, J., Real equiangular lines in dimension 18 and the De Caen-Jacobi identity for complementary subgraphs (2022) |
| [22] | Greaves, G.; Syatriadi, J.; Yatsyna, P., Equiangular lines in Euclidean spaces: dimensions 17 and 18 (2022) |
| [23] | Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616 (1995) · Zbl 0831.05044 |
| [24] | Hirschfeld, W. P.; Storme, L., The packing problem in statistics, coding theory and finite projective spaces: update 2001, (Blokhuis, A.; Hirschfeld, J. W.P.; Jungnickel, D.; Thas, J. A., Finite Geometries (2001), Kluwer: Kluwer Dordrecht), 201-246 · Zbl 1025.51012 |
| [25] | Keevash, P., The existence of designs (2014) |
| [26] | Knuth, D. E., The Art of Computer Programming, vol. 1 (2005), Addison-Wesley: Addison-Wesley Upper Saddle River, NJ · Zbl 0191.17903 |
| [27] | Krivelevich, M.; Sudakov, B., Pseudo-random graphs, (Bolyai Soc. Math. Stud., vol. 15 (2006), Springer: Springer Berlin), 199-262 · Zbl 1098.05075 |
| [28] | Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146 (1999) · Zbl 0918.05062 |
| [29] | Mubayi, D.; Verstraëte, J., A note on pseudorandom Ramsey graphs (2019) |
| [30] | Radziszowski, S.; Xiaodong, X., On the most wanted Folkman graph, Geombinatorics, XVI, 367-381 (2007) · Zbl 1506.05137 |
| [31] | Shi, G.; Dong, D.; Petersen, I. R.; Johansson, K. H., Reaching a quantum consensus: master equations that generate symmetrization and synchronization, IEEE Trans. Autom. Control, 61, 2, 374-387 (2016) · Zbl 1359.81073 |
| [32] | Taylor, D. E., The Geometry of the Classical Groups (1992), Heldermann: Heldermann Berlin · Zbl 0767.20001 |
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.
