Oriented Cycles in Digraphs of Large Outdegree View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-05-19

AUTHORS

Lior Gishboliner, Raphael Steiner, Tibor Szabó

ABSTRACT

In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ.We prove this conjecture and answer further open questions raised by Aboulker et al. More... »

PAGES

1-43

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-021-4750-z

DOI

http://dx.doi.org/10.1007/s00493-021-4750-z

DIMENSIONS

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


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": "Department of Mathematics, ETH, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Mathematics, ETH, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gishboliner", 
        "givenName": "Lior", 
        "id": "sg:person.011262470301.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011262470301.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Departement of Computer Science, ETH, Zu\u00e4rich, Switzerland", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institute of Mathematics, Technische Universit\u00e4at Berlin, Berlin, Germany", 
            "Departement of Computer Science, ETH, Zu\u00e4rich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Steiner", 
        "givenName": "Raphael", 
        "id": "sg:person.013305342541.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013305342541.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics, Freie Universit\u00e4t Berlin, Berlin, Germany", 
          "id": "http://www.grid.ac/institutes/grid.14095.39", 
          "name": [
            "Institute of Mathematics, Freie Universit\u00e4t Berlin, Berlin, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szab\u00f3", 
        "givenName": "Tibor", 
        "id": "sg:person.016701574661.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016701574661.34"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01275674", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032841904", 
          "https://doi.org/10.1007/bf01275674"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01261316", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028669841", 
          "https://doi.org/10.1007/bf01261316"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-84800-998-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047271474", 
          "https://doi.org/10.1007/978-1-84800-998-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579195", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007252638", 
          "https://doi.org/10.1007/bf02579195"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01192525", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014026001", 
          "https://doi.org/10.1007/bf01192525"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579379", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021426855", 
          "https://doi.org/10.1007/bf02579379"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01364272", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010503966", 
          "https://doi.org/10.1007/bf01364272"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-05-19", 
    "datePublishedReg": "2022-05-19", 
    "description": "In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomass\u00e9 studied special cases of Mader\u2019s problem and made the following conjecture: for every \u2113 \u2265 2 there exists K = K(\u2113) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length \u2113.We prove this conjecture and answer further open questions raised by Aboulker et al.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-021-4750-z", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }
    ], 
    "keywords": [
      "cases", 
      "subdivision", 
      "cycle", 
      "length", 
      "open question", 
      "Cohen", 
      "questions", 
      "et al", 
      "problem", 
      "Mader", 
      "digraph D", 
      "Moura", 
      "orientation", 
      "al", 
      "cycle of length", 
      "conjecture", 
      "vertices", 
      "special case", 
      "following conjecture", 
      "outdegree", 
      "digraphs", 
      "Havet", 
      "digraph F", 
      "Thomass\u00e9", 
      "Oriented Cycles", 
      "large outdegree"
    ], 
    "name": "Oriented Cycles in Digraphs of Large Outdegree", 
    "pagination": "1-43", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1147999041"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-021-4750-z"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-021-4750-z", 
      "https://app.dimensions.ai/details/publication/pub.1147999041"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T21:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_947.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-021-4750-z"
  }
]
 

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-4750-z'

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-4750-z'

Turtle is a human-readable linked data format.

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

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-4750-z'


 

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

126 TRIPLES      21 PREDICATES      55 URIs      40 LITERALS      4 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-021-4750-z schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N4636a968b02241429583e2ca47f819db
4 schema:citation sg:pub.10.1007/978-1-84800-998-1
5 sg:pub.10.1007/bf01192525
6 sg:pub.10.1007/bf01261316
7 sg:pub.10.1007/bf01275674
8 sg:pub.10.1007/bf01364272
9 sg:pub.10.1007/bf02579195
10 sg:pub.10.1007/bf02579379
11 schema:datePublished 2022-05-19
12 schema:datePublishedReg 2022-05-19
13 schema:description In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ.We prove this conjecture and answer further open questions raised by Aboulker et al.
14 schema:genre article
15 schema:isAccessibleForFree true
16 schema:isPartOf sg:journal.1136493
17 schema:keywords Cohen
18 Havet
19 Mader
20 Moura
21 Oriented Cycles
22 Thomassé
23 al
24 cases
25 conjecture
26 cycle
27 cycle of length
28 digraph D
29 digraph F
30 digraphs
31 et al
32 following conjecture
33 large outdegree
34 length
35 open question
36 orientation
37 outdegree
38 problem
39 questions
40 special case
41 subdivision
42 vertices
43 schema:name Oriented Cycles in Digraphs of Large Outdegree
44 schema:pagination 1-43
45 schema:productId N914920f153a34c05b387d7d138a9c1e0
46 Neac6b7de164a4f6790c645948662937e
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1147999041
48 https://doi.org/10.1007/s00493-021-4750-z
49 schema:sdDatePublished 2022-11-24T21:09
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nbf2d8e274db241bfb89b414b0950b36f
52 schema:url https://doi.org/10.1007/s00493-021-4750-z
53 sgo:license sg:explorer/license/
54 sgo:sdDataset articles
55 rdf:type schema:ScholarlyArticle
56 N4636a968b02241429583e2ca47f819db rdf:first sg:person.011262470301.91
57 rdf:rest Nb73e30eaf4264b2c88c3b2b985f978bb
58 N914920f153a34c05b387d7d138a9c1e0 schema:name dimensions_id
59 schema:value pub.1147999041
60 rdf:type schema:PropertyValue
61 Nb73e30eaf4264b2c88c3b2b985f978bb rdf:first sg:person.013305342541.10
62 rdf:rest Nf860e0372667450aab267bcb65fd941a
63 Nbf2d8e274db241bfb89b414b0950b36f schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Neac6b7de164a4f6790c645948662937e schema:name doi
66 schema:value 10.1007/s00493-021-4750-z
67 rdf:type schema:PropertyValue
68 Nf860e0372667450aab267bcb65fd941a rdf:first sg:person.016701574661.34
69 rdf:rest rdf:nil
70 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
71 schema:name Mathematical Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
74 schema:name Pure Mathematics
75 rdf:type schema:DefinedTerm
76 sg:journal.1136493 schema:issn 0209-9683
77 1439-6912
78 schema:name Combinatorica
79 schema:publisher Springer Nature
80 rdf:type schema:Periodical
81 sg:person.011262470301.91 schema:affiliation grid-institutes:grid.5801.c
82 schema:familyName Gishboliner
83 schema:givenName Lior
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011262470301.91
85 rdf:type schema:Person
86 sg:person.013305342541.10 schema:affiliation grid-institutes:None
87 schema:familyName Steiner
88 schema:givenName Raphael
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013305342541.10
90 rdf:type schema:Person
91 sg:person.016701574661.34 schema:affiliation grid-institutes:grid.14095.39
92 schema:familyName Szabó
93 schema:givenName Tibor
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016701574661.34
95 rdf:type schema:Person
96 sg:pub.10.1007/978-1-84800-998-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047271474
97 https://doi.org/10.1007/978-1-84800-998-1
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bf01192525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014026001
100 https://doi.org/10.1007/bf01192525
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/bf01261316 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028669841
103 https://doi.org/10.1007/bf01261316
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bf01275674 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032841904
106 https://doi.org/10.1007/bf01275674
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf01364272 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010503966
109 https://doi.org/10.1007/bf01364272
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/bf02579195 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007252638
112 https://doi.org/10.1007/bf02579195
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/bf02579379 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021426855
115 https://doi.org/10.1007/bf02579379
116 rdf:type schema:CreativeWork
117 grid-institutes:None schema:alternateName Departement of Computer Science, ETH, Zuärich, Switzerland
118 schema:name Departement of Computer Science, ETH, Zuärich, Switzerland
119 Institute of Mathematics, Technische Universitäat Berlin, Berlin, Germany
120 rdf:type schema:Organization
121 grid-institutes:grid.14095.39 schema:alternateName Institute of Mathematics, Freie Universität Berlin, Berlin, Germany
122 schema:name Institute of Mathematics, Freie Universität Berlin, Berlin, Germany
123 rdf:type schema:Organization
124 grid-institutes:grid.5801.c schema:alternateName Department of Mathematics, ETH, Zürich, Switzerland
125 schema:name Department of Mathematics, ETH, Zürich, Switzerland
126 rdf:type schema:Organization
 




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


...