---
_id: '10335'
abstract:
- lang: eng
  text: "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.\r\nEquality 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."
acknowledgement: 'V. K. gratefully acknowledges the support of Austrian Science Fund
  (FWF): P 30902-N35. This work was done mostly while he was employed at the University
  of Innsbruck. During the early stage of this research, V. K. was partially supported
  by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y
  of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University
  project UNCE/SCI/004.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vojtech
  full_name: Kaluza, Vojtech
  id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
  last_name: Kaluza
  orcid: 0000-0002-2512-8698
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
citation:
  ama: Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations
    of graphs. <i>Combinatorica</i>. 2022;42:1317-1345. doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a>
  apa: Kaluza, V., &#38; Tancer, M. (2022). Even maps, the Colin de Verdière number
    and representations of graphs. <i>Combinatorica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a>
  chicago: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
    and Representations of Graphs.” <i>Combinatorica</i>. Springer Nature, 2022. <a
    href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a>.
  ieee: V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations
    of graphs,” <i>Combinatorica</i>, vol. 42. Springer Nature, pp. 1317–1345, 2022.
  ista: Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations
    of graphs. Combinatorica. 42, 1317–1345.
  mla: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
    and Representations of Graphs.” <i>Combinatorica</i>, 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>.
  short: V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.
corr_author: '1'
date_created: 2021-11-25T13:49:16Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2024-10-09T20:53:51Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s00493-021-4443-7
external_id:
  arxiv:
  - '1907.05055'
  isi:
  - '000798210100003'
fulldoi: https://doi.org/10.1007/s00493-021-4443-7
intvolume: '        42'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.1907.05055'
month: '12'
oa: 1
oa_version: Preprint
page: 1317-1345
publication: Combinatorica
publication_identifier:
  issn:
  - 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Even maps, the Colin de Verdière number and representations of graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2022'
...