KIT | KIT-Bibliothek | Impressum | Datenschutz

On Graphs Embeddable in a Layer of a Hypercube and Their Extremal Numbers

Axenovich, Maria 1; Martin, Ryan R.; Winter, Christian ORCID iD icon 2
1 Karlsruher Institut für Technologie (KIT)
2 Institut für Algebra und Geometrie (IAG), Karlsruher Institut für Technologie (KIT)

Abstract:

A graph is cubical if it is a subgraph of a hypercube. For a
cubical graph H and a hypercube Q$_n$, ex(Q$_n$, H) is the largest number
of edges in an H-free subgraph of Q$_n$. If ex(Q$_n$, H) is at least a positive
proportion of the number of edges in Q$_n$, then H is said to have positive
Tur´an density in the hypercube; otherwise it has zero Tur´an density.
Determining ex(Q$_n$, H) and even identifying whether H has positive or
zero Tur´an density remains a widely open question for general H. In
this paper we focus on layered graphs, i.e., graphs that are contained in
an edge layer of some hypercube. Graphs H that are not layered have
positive Tur´an density because one can form an H-free subgraph of Q$_n$
consisting of edges of every other layer. For example, a 4-cycle is not
layered and has positive Tur´an density. However, in general, it is not
obvious what properties layered graphs have. We give a characterization
of layered graphs in terms of edge-colorings. We show that most non-
trivial subdivisions have zero Tur´an density, extending known results on
zero Tur´an density of even cycles of length at least 12 and of length
... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000173663
Veröffentlicht am 26.08.2024
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2024
Sprache Englisch
Identifikator ISSN: 0218-0006, 0219-3094
KITopen-ID: 1000173663
Erschienen in Annals of Combinatorics
Verlag Springer
Vorab online veröffentlicht am 29.07.2024
Nachgewiesen in Web of Science
Dimensions
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page