On generalized shift graphs

Christian Avart, Tomasz Łuczak, and Vojtěch Rödl. "On generalized shift graphs." Fundamenta Mathematicae 226.2 (2014): 173-199. <http://eudml.org/doc/283046>.

@article{ChristianAvart2014,
abstract = {In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets $A = \{a₁,...,a_\{k\}\}$ and $B = \{b₁,...,b_\{k\}\}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_\{k-1\} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_\{(l)\}|V(F|$, where $log_\{(l)\}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.},
author = {Christian Avart, Tomasz Łuczak, Vojtěch Rödl},
journal = {Fundamenta Mathematicae},
keywords = {shift graphs; chromatic number; infinite graphs; odd girth},
language = {eng},
number = {2},
pages = {173-199},
title = {On generalized shift graphs},
url = {http://eudml.org/doc/283046},
volume = {226},
year = {2014},
}

TY - JOUR
AU - Christian Avart
AU - Tomasz Łuczak
AU - Vojtěch Rödl
TI - On generalized shift graphs
JO - Fundamenta Mathematicae
PY - 2014
VL - 226
IS - 2
SP - 173
EP - 199
AB - In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets $A = {a₁,...,a_{k}}$ and $B = {b₁,...,b_{k}}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_{k-1} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_{(l)}|V(F|$, where $log_{(l)}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.
LA - eng
KW - shift graphs; chromatic number; infinite graphs; odd girth
UR - http://eudml.org/doc/283046
ER -