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/bf02579379", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021426855", 
          "https://doi.org/10.1007/bf02579379"
        ], 
        "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/bf01261316", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028669841", 
          "https://doi.org/10.1007/bf01261316"
        ], 
        "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/bf01275674", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032841904", 
          "https://doi.org/10.1007/bf01275674"
        ], 
        "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/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-10-01T06:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_932.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 N0382db34e0c54a2e940ae0df53e271bd
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 N5591fbfd7b9142b4bd5cdf7a7190d260
46 N667cc2ee7eb64966b0305e5b8267c486
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-10-01T06:50
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N980e8223ad9f45c081f901c55e244164
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 N0382db34e0c54a2e940ae0df53e271bd rdf:first sg:person.011262470301.91
57 rdf:rest N3be3c95bf6a444f09278d76a7fbe52ab
58 N3be3c95bf6a444f09278d76a7fbe52ab rdf:first sg:person.013305342541.10
59 rdf:rest N4880faad5c3c4f758ff5b06bd0375105
60 N4880faad5c3c4f758ff5b06bd0375105 rdf:first sg:person.016701574661.34
61 rdf:rest rdf:nil
62 N5591fbfd7b9142b4bd5cdf7a7190d260 schema:name doi
63 schema:value 10.1007/s00493-021-4750-z
64 rdf:type schema:PropertyValue
65 N667cc2ee7eb64966b0305e5b8267c486 schema:name dimensions_id
66 schema:value pub.1147999041
67 rdf:type schema:PropertyValue
68 N980e8223ad9f45c081f901c55e244164 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
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)


...