On the bandwidth of the Kneser graph. (English) Zbl 1365.05089
Summary: Let \(G = (V, E)\) be a graph on \(n\) vertices and \(f : V \rightarrow [1, n]\) a one to one map of \(V\) onto the integers 1 through \(n\). Let be \(\text{dilation}(f) = \max\{| f(v) - f(w) | : v w \in E \}\). Define the bandwidth \(B(G)\) of \(G\) to be the minimum possible value of \(\text{dilation}(f)\) over all such one to one maps \(f\). Next define the Kneser graph \(K(n, r)\) to be the graph with vertex set \(\binom{[n]}{r}\), the collection of \(r\)-subsets of an \(n\) element set, and edge set \(E = \{A B : A, B \in \binom{[n]}{r}, A \cap B = \emptyset \}\). For fixed \(r \geq 4\) and \(n\) growing we show that
\[ B(K(n, r)) = \binom{n - 1}{r}+ \frac{1}{2} \binom{n - 4}{r - 1}- \frac{1}{2} \binom{n - 1}{r - 2} + O(n^{r - 4}) . \]
\[ B(K(n, r)) = \binom{n - 1}{r}+ \frac{1}{2} \binom{n - 4}{r - 1}- \frac{1}{2} \binom{n - 1}{r - 2} + O(n^{r - 4}) . \]
References:
| [1] | Allen, Peter; Brightwell, Graham; Skokan, Jozef, Ramsey-goodness—and otherwise, Combinatorica, 33, 2, 125-160 (2013) · Zbl 1324.05130 |
| [2] | Assmann, S. F.; Peck, G. W.; Sysł o, M. M.; Zak, J., The bandwidth of caterpillars with hairs of length \(1\) and \(2\), SIAM J. Algebr. Discrete Methods, 2, 4, 387-393 (1981) · Zbl 0494.05059 |
| [3] | Bárány, I., A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A, 25, 3, 325-326 (1978) · Zbl 0404.05028 |
| [4] | Bollobás, B.; Daykin, D. E.; Erdös, P., Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. (2), 27, 105, 25-32 (1976) · Zbl 0337.05135 |
| [5] | Böttcher, Julia; Pruessmann, Klaas P.; Taraz, Anusch; Würfl, Andreas, Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs, European J. Combin., 31, 5, 1217-1227 (2010) · Zbl 1231.05082 |
| [6] | Böttcher, Julia; Schacht, Mathias; Taraz, Anusch, Proof of the bandwidth conjecture of Bollobás and Komlós, Math. Ann., 343, 1, 175-205 (2009) · Zbl 1229.05132 |
| [7] | Chen, Ya-Chen, Triangle-free Hamiltonian Kneser graphs, J. Combin. Theory Ser. B, 89, 1, 1-16 (2003) · Zbl 1030.05069 |
| [8] | Chung, F. R.K., Labelings of graphs, (Selected Topics in Graph Theory, vol. 3 (1988), Academic Press: Academic Press San Diego, CA), 151-168 · Zbl 0656.05058 |
| [9] | Chvátalová, J., On the Bandwidth Problem for Graphs (1980), University of Waterloo, (Ph.D. thesis) · Zbl 0603.05042 |
| [10] | Cuthill, E.; McKee, J., Reducing the bandwidth of sparse symmetric matrices, (Proc. 24th Natl Conf. ACM (1969)), 151-172 |
| [11] | Daubey, C.; Feige, U.; Unger, W., Hardness results for approximating bandwidth, J. Comput. System Sci., 77, 111-132 (2010) |
| [12] | Diaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Comput. Surv., 34, 3, 313-356 (2002) |
| [13] | Dolnikov, V. L., Transversals of families of sets in \(R^n\) and a relationship between Helly and Borsuk theorems, Mat. Sb., 184, 5, 111-132 (1993) · Zbl 0818.52006 |
| [14] | Erdös, P., A problem on independent \(r\)-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 8, 93-95 (1965) · Zbl 0136.21302 |
| [15] | Erdös, P.; Ko, Chao; Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), 12, 313-320 (1961) · Zbl 0100.01902 |
| [16] | Feige, U.; Talwar, K., Approximating the bandwidth of caterpillars, Algorithmica, 55, 1, 190-204 (2009) · Zbl 1194.68170 |
| [17] | Frankl, P., The Erdos-Ko-Rado theorem is true for \(n = c k t\), (Combinatorial Proc. Fifth Hungarian Coll. Combinatorics (1978)), 365-375 · Zbl 0401.05001 |
| [18] | Frankl, Peter, Improved bounds for Erdös’ matching conjecture, J. Combin. Theory Ser. A, 120, 5, 1068-1072 (2013) · Zbl 1277.05123 |
| [19] | Frankl, Peter; Łuczak, Tomasz; Mieczkowska, Katarzyna, On matchings in hypergraphs, Electron. J. Combin., 19, 2 (2012) · Zbl 1252.05092 |
| [20] | Frankl, Peter; Rödl, Vojtech; Ruciński, Andrzej, On the maximum number of edges in a triple system not containing a disjoint family of a given size, Combin. Probab. Comput., 21, 1-2, 141-148 (2012) · Zbl 1241.05053 |
| [21] | Frankl, Peter; Tokushige, Norihide, Some best possible inequalities concerning cross-intersecting families, J. Combin. Theory Ser. A, 61, 1, 87-97 (1992) · Zbl 0767.05093 |
| [22] | Füredi, Zoltán, Cross-intersecting families of finite sets, J. Combin. Theory Ser. A, 72, 2, 332-339 (1995) · Zbl 0839.05092 |
| [23] | Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E., Complexity results for bandwidth minimization, SIAM J. Appl. Math., 34, 3, 477-495 (1978) · Zbl 0385.05048 |
| [25] | Greene, Joshua E., A new short proof of Kneser’s conjecture, Amer. Math. Monthly, 109, 10, 918-920 (2002) · Zbl 1023.05014 |
| [26] | Harper, L. H., Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory, 1, 385-393 (1966) · Zbl 0158.20802 |
| [28] | Hilton, A. J.W.; Milner, E. C., Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), 18, 369-384 (1967) · Zbl 0168.26205 |
| [29] | Huang, Hao; Loh, Po-Shen; Sudakov, Benny, The size of a hypergraph and its matching number, Combin. Probab. Comput., 21, 3, 442-450 (2012) · Zbl 1242.05268 |
| [30] | Jiang, Tao; Perkel, Manley; Pritikin, Dan, Arrangements of \(k\)-sets with intersection constraints, European J. Combin., 33, 8, 1882-1899 (2012) · Zbl 1252.05104 |
| [31] | Juvan, Martin; Mohar, Bojan, Laplace eigenvalues and bandwidth-type invariants of graphs, J. Graph Theory, 17, 3, 393-407 (1993) · Zbl 0785.05077 |
| [32] | Karpinski, M.; Wirtgen, J.; Zelikovsky, A., An approximation algorithm for bandwidth on dense graphs, Electron. Colloquium Comput. Complexity, 4, 17 (1997) |
| [33] | Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028 |
| [34] | Lovász, László, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 |
| [35] | Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H., Topological bandwidth, SIAM J. Algebr. Discrete Methods, 6, 3, 418-444 (1985) · Zbl 0573.05052 |
| [36] | Matoušek, Jiři, A combinatorial proof of Kneser’s conjecture, Combinatorica, 24, 1, 163-170 (2004) · Zbl 1047.05018 |
| [37] | Miller, Z., The bandwidth of caterpillar graphs, (Proceedings of the 12’th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, vol. 33 (1981)), 235-252 · Zbl 0504.05028 |
| [38] | Miller, Z., A linear algorithm for topological bandwidth in degree 3 trees, SIAM J. Comput., 17, 5, 1018-1035 (1988) · Zbl 0662.68072 |
| [39] | Mohammadyari, R.; Darafsheh, M. R., Topological indices of the kneser graph, Filomat, 26, 4, 665-672 (2012) · Zbl 1289.05134 |
| [40] | Monien, Burkhard, The bandwidth minimization problem for caterpillars with hair length 3 is np-complete, SIAM J. Algebr. Discrete Methods, 7, 4, 505-512 (1986) · Zbl 0624.68059 |
| [41] | Mota, G. O.; Sárközy, G. N.; Schacht, M.; Taraz, A., Ramsey numbers for bipartite graphs with small bandwidth, European J. Combin., 48, 165-176 (2015) · Zbl 1315.05089 |
| [42] | Papadimitriou, Ch. H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 3, 263-270 (1976) · Zbl 0321.65019 |
| [43] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company · Zbl 1002.65042 |
| [44] | Simon, Horst D.; Teng, Shang-Hua, How good is recursive bisection?, SIAM J. Sci. Comput., 18, 5, 1436-1445 (1997) · Zbl 0886.68104 |
| [45] | Valencia-Pabon, Mario; Vera, Juan-Carlos, On the diameter of Kneser graphs, Discrete Math., 305, 1-3, 383-385 (2005) · Zbl 1100.05030 |
| [46] | van Dam, E. R.; Sotirov, R., On bounding the bandwidth of graphs with symmetry, INFORMS J. Comput., 27, 1, 75-88 (2015) · Zbl 1327.90359 |
| [48] | Wilson, Richard M., The exact bound in the Erdös-Ko-Rado theorem, Combinatorica, 4, 2-3, 247-257 (1984) · Zbl 0556.05039 |
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.
