Even Maps, the Colin de Verdière Number and Representations of Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-05-19

AUTHORS

Vojtěch Kaluža, Martin Tancer

ABSTRACT

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. More... »

PAGES

1-29

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-021-4443-7

DOI

http://dx.doi.org/10.1007/s00493-021-4443-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1147999040


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Science and Technology, Klosterneuburg, Austria", 
          "id": "http://www.grid.ac/institutes/grid.33565.36", 
          "name": [
            "Institute of Science and Technology, Klosterneuburg, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kalu\u017ea", 
        "givenName": "Vojt\u011bch", 
        "id": "sg:person.011514021153.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011514021153.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Applied Mathematics, Charles University, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of Applied Mathematics, Charles University, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tancer", 
        "givenName": "Martin", 
        "id": "sg:person.014745454710.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014745454710.53"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s11856-010-0070-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003323849", 
          "https://doi.org/10.1007/s11856-010-0070-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-41498-5_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053449848", 
          "https://doi.org/10.1007/978-3-642-41498-5_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01195002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006363940", 
          "https://doi.org/10.1007/bf01195002"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00493-009-2219-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040087258", 
          "https://doi.org/10.1007/s00493-009-2219-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01344542", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003824109", 
          "https://doi.org/10.1007/bf01344542"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009821", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013749403", 
          "https://doi.org/10.1007/pl00009821"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-05-19", 
    "datePublishedReg": "2022-05-19", 
    "description": "Van der Holst and Pendavingh introduced a graph parameter \u03c3, which coincides with the more famous Colin de Verdi\u00e8re graph parameter \u03bc for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved \u03bc(G) \u2264 \u03c3(G) + 2 and conjectured \u03c3(G) \u2264 \u03c3(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on \u03c3(G) which is, in general, tight.Equality between \u03bc and \u03c3 does not hold in general as van der Holst and Pendavingh showed that there is a graph G with \u03bc(G) \u2264 18 and \u03c3(G) \u2265 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which \u03bc(H) \u2265 7 and \u03c3(H) \u2265 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy \u03bc(Hq) \u2208 O(q3/2) and \u03c3(Hq) \u2265 q2.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-021-4443-7", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }
    ], 
    "keywords": [
      "van der Holst", 
      "finite projective plane", 
      "embeddability property", 
      "small values", 
      "parameter \u03bc", 
      "representations of graphs", 
      "graph G.", 
      "Verdi\u00e8re number", 
      "graph H", 
      "parameter \u03c3", 
      "graph G", 
      "q satisfies", 
      "projective plane", 
      "graph", 
      "Pendavingh", 
      "Colin", 
      "conjecture", 
      "Holst", 
      "satisfies", 
      "upper", 
      "representation", 
      "plane", 
      "G.", 
      "properties", 
      "gap", 
      "values", 
      "equality", 
      "maps", 
      "number", 
      "Q2", 
      "definition", 
      "Van", 
      "HQ"
    ], 
    "name": "Even Maps, the Colin de Verdi\u00e8re Number and Representations of Graphs", 
    "pagination": "1-29", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1147999040"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-021-4443-7"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-021-4443-7", 
      "https://app.dimensions.ai/details/publication/pub.1147999040"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T16:08", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_940.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-021-4443-7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4443-7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4443-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4443-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4443-7'


 

This table displays all metadata directly associated to this object as RDF triples.

118 TRIPLES      21 PREDICATES      61 URIs      47 LITERALS      4 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-021-4443-7 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nd1f0983c22a642f2b58d335506cb7ab0
4 schema:citation sg:pub.10.1007/978-3-642-41498-5_10
5 sg:pub.10.1007/bf01195002
6 sg:pub.10.1007/bf01344542
7 sg:pub.10.1007/pl00009821
8 sg:pub.10.1007/s00493-009-2219-6
9 sg:pub.10.1007/s11856-010-0070-5
10 schema:datePublished 2022-05-19
11 schema:datePublishedReg 2022-05-19
12 schema:description 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.
13 schema:genre article
14 schema:isAccessibleForFree true
15 schema:isPartOf sg:journal.1136493
16 schema:keywords Colin
17 G.
18 HQ
19 Holst
20 Pendavingh
21 Q2
22 Van
23 Verdière number
24 conjecture
25 definition
26 embeddability property
27 equality
28 finite projective plane
29 gap
30 graph
31 graph G
32 graph G.
33 graph H
34 maps
35 number
36 parameter μ
37 parameter σ
38 plane
39 projective plane
40 properties
41 q satisfies
42 representation
43 representations of graphs
44 satisfies
45 small values
46 upper
47 values
48 van der Holst
49 schema:name Even Maps, the Colin de Verdière Number and Representations of Graphs
50 schema:pagination 1-29
51 schema:productId N1c188e5a5fbe4132a8a85b6647cd2b93
52 N54174642be904675b0ead96209dbefdc
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1147999040
54 https://doi.org/10.1007/s00493-021-4443-7
55 schema:sdDatePublished 2022-09-02T16:08
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N447c7eff80594633b64893bcf9fd4ecc
58 schema:url https://doi.org/10.1007/s00493-021-4443-7
59 sgo:license sg:explorer/license/
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N1c188e5a5fbe4132a8a85b6647cd2b93 schema:name doi
63 schema:value 10.1007/s00493-021-4443-7
64 rdf:type schema:PropertyValue
65 N2f035f77ebef481c9880cb4a111ddd23 rdf:first sg:person.014745454710.53
66 rdf:rest rdf:nil
67 N447c7eff80594633b64893bcf9fd4ecc schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N54174642be904675b0ead96209dbefdc schema:name dimensions_id
70 schema:value pub.1147999040
71 rdf:type schema:PropertyValue
72 Nd1f0983c22a642f2b58d335506cb7ab0 rdf:first sg:person.011514021153.36
73 rdf:rest N2f035f77ebef481c9880cb4a111ddd23
74 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
75 schema:name Mathematical Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
78 schema:name Pure Mathematics
79 rdf:type schema:DefinedTerm
80 sg:journal.1136493 schema:issn 0209-9683
81 1439-6912
82 schema:name Combinatorica
83 schema:publisher Springer Nature
84 rdf:type schema:Periodical
85 sg:person.011514021153.36 schema:affiliation grid-institutes:grid.33565.36
86 schema:familyName Kaluža
87 schema:givenName Vojtěch
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011514021153.36
89 rdf:type schema:Person
90 sg:person.014745454710.53 schema:affiliation grid-institutes:grid.4491.8
91 schema:familyName Tancer
92 schema:givenName Martin
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014745454710.53
94 rdf:type schema:Person
95 sg:pub.10.1007/978-3-642-41498-5_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053449848
96 https://doi.org/10.1007/978-3-642-41498-5_10
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/bf01195002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006363940
99 https://doi.org/10.1007/bf01195002
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/bf01344542 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003824109
102 https://doi.org/10.1007/bf01344542
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/pl00009821 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013749403
105 https://doi.org/10.1007/pl00009821
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/s00493-009-2219-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040087258
108 https://doi.org/10.1007/s00493-009-2219-6
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/s11856-010-0070-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003323849
111 https://doi.org/10.1007/s11856-010-0070-5
112 rdf:type schema:CreativeWork
113 grid-institutes:grid.33565.36 schema:alternateName Institute of Science and Technology, Klosterneuburg, Austria
114 schema:name Institute of Science and Technology, Klosterneuburg, Austria
115 rdf:type schema:Organization
116 grid-institutes:grid.4491.8 schema:alternateName Department of Applied Mathematics, Charles University, Prague, Czech Republic
117 schema:name Department of Applied Mathematics, Charles University, Prague, Czech Republic
118 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...