Topological Bounds for Graph Representations over Any Field
Pages 91 - 104
Abstract
Haviv [European J. Combin., 81 (2019), pp. 84--97] has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb{R}$. We show that this actually holds for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $\mathbb{R}$---an important graph invariant from coding theory---and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.
References
[1]
M. Alishahi and H. Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory Ser. B, 115 (2015), pp. 186--209.
[2]
M. Alishahi and H. Hajiabolhassan, A generalization of Gale's lemma, J. Graph Theory, 88 (2018), pp. 337--346.
[3]
M. Alishahi, H. Hajiabolhassan, and F. Meunier, Strengthening topological colorful results for graphs, European J. Combin., 64 (2017), pp. 27--44.
[4]
N. Alon and M. Krivelevich, Constructive bounds for a Ramsey-type problem, Graphs Combin., 13 (1997), pp. 217--225.
[5]
I. Bárány, A short proof of Kneser's conjecture, J. Combin. Theory Ser. A, 25 (1978), pp. 325--326.
[6]
H. R. Daneshpajouh, F. Meunier, and G. Mizrahi, Colorings of Complements of Line Graphs, preprint, https://arxiv.org/abs/2003.08255, 2020.
[7]
V. L. Dol'nikov, A certain combinatorial inequality, Sib. Math. J., 29 (1988), pp. 375--379.
[8]
P. Erdös, Z. Füredi, A. Hajnal, P. Komjáth, V. Rödl, and A. Seress, Coloring graphs with locally few colors, Discrete Math., 59 (1986), pp. 21--34.
[9]
K. Fan, A generalization of Tucker's combinatorial lemma with topological applications, Ann. of Math. (2), 56 (1952), pp. 431--437.
[10]
M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman, San Francisco, 1979.
[11]
W. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 231--232.
[12]
I. Haviv, Approximating the orthogonality dimension of graphs and hypergraphs, in Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 2019, 39.
[13]
I. Haviv, Topological bounds on the dimension of orthogonal representations of graphs, European J. Combin., 81 (2019), pp. 84--97.
[14]
Y. Li and Z. Zhang, A note on eigenvalue bounds for independence numbers of non-regular graphs, Discrete Appl. Math., 174 (2014), pp. 146--149.
[15]
L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978), pp. 319--324.
[16]
L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 1--7.
[17]
L. Lovász, Graphs and Geometry, Amer. Math. Soc. Colloq. Publ. 65, AMS, Providence, RI, 2019.
[18]
L. Lovász and K. Vesztergombi, Geometric Representations of Graphs, Paul Erdös and His Mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 471--498.
[19]
J. Matoušek, Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in Combinatorics and Geometry, Written in cooperation with Anders Björner and Günter M. Ziegler, Universitext, Springer-Verlag, Berlin, 2003.
[20]
J. Matoušek and G. M. Ziegler, Topological lower bounds for the chromatic number: A hierarchy, Jahresber. Deutsch. Math.-Verein., 106 (2004), pp. 71--90.
[21]
R. Peeters, Orthogonal representations over finite fields and the chromatic number of graphs, Combinatorica, 16 (1996), pp. 417--431.
[22]
R. Peeters, The maximum edge biclique problem is \textupNP-complete, Discrete Appl. Math., 131 (2003), pp. 651--654.
[23]
K. Shanmugam, A. G. Dimakis, and M. Langberg, Local graph coloring and index coding, in Proceedings of the 2013 IEEE International Symposium on Information Theory, IEEE, 2013, pp. 1152--1156.
[24]
G. Simonyi, C. Tardif, and A. Zsbán, Colourful theorems and indices of homomorphism complexes, Electron. J. Combin., 20 (2013), 10.
[25]
G. Simonyi and G. Tardos, Local chromatic number, Ky Fan's theorem, and circular colorings, Combinatorica, 26 (2006), pp. 587--626.
[26]
A. W. Tucker, Some topological properties of disk and sphere, in Proceedings of the First Canadian Math. Congress, Montréal, 1945, University of Toronto Press, Toronto, ON, 1946, pp. 285--309.
Recommendations
On the topological lower bound for the multichromatic number
In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser's conjecture, which was proved by Lovasz in 1978 [10]. Here we show that Lovasz's ...
Exact bounds on the order of the maximum clique of a graph
The paper reviews some of the existing exact bounds to the maximum clique of a graph and successively presents a new upper and a new lower bound. The new upper bound is ω ≤ n - rank oA/2, where oA is the adjacency matrix of the complementary graph, and ...
Topological Inductive Constructions for Tight Surface Graphs
AbstractWe investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for -tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjdmec.35.1
Issue’s Table of Contents© 2021, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2021
Author Tags
Author Tag
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in