Even maps, the Colin de Verdière number and representations of graphs

article Even maps, the Colin de Verdière number and representations of graphs published yes Vojtech Kaluza author 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E0000-0002-2512-8698 Martin Tancer author 38AC689C-F248-11E8-B48F-1D18A9856A870000-0002-1191-6714 UlWa department Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight. Equality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2. Springer Nature2022 eng Combinatorica 0209-9683 1907.05055 00079821010000310.1007/s00493-021-4443-7 421317-1345 Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 42, 1317–1345. Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica, vol. 42, Springer Nature, 2022, pp. 1317–45, doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a>. Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. Springer Nature. <a href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a> Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica. Springer Nature, 2022. <a href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a>. Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 2022;42:1317-1345. doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a> V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations of graphs,” Combinatorica, vol. 42. Springer Nature, pp. 1317–1345, 2022. V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345. 103352021-11-25T13:49:16Z2024-10-09T20:53:51Z