On generalized shift graphs

Christian Avart ¹   ; Tomasz Łuczak ²   ; Vojtěch Rödl ³

¹ Department of Mathematics and Statistics Georgia State University Atlanta, GA 30303, U.S.A.
² Faculty of Mathematics and CS Adam Mickiewicz University 61-614 Poznań, Poland
³ Department of Mathematics and CS Emory University Atlanta, GA 30322, U.S.A.

Fundamenta Mathematicae, Tome 226 (2014) no. 2, pp. 173-199

Résumé

In 1968 Erd{ő}s and Hajnal introduced shift graphs as graphs whose vertices are the $k$-element subsets of $[n]=\{1,\dots ,n\}$ (or of an infinite cardinal $\kappa $) and with two $k$-sets $A=\{a_1,\dots ,a_{k}\}$ and $B=\{b_1,\dots ,b_{k}\}$ joined if $a_1 a_2=b_1 a_3=b_2 \cdots 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 $\kappa $ and integer $l$, there exists a graph $G$ with $|V(G)|=\chi (G)=\kappa $ but such that, for any finite subgraph $F\subset G$, $\chi (F)\leq \log_{(l)}|V(F|$, where $\log_{(l)}$ is the $l$-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.

Détail

DOI : 10.4064/fm226-2-6

Keywords: erd hajnal introduced shift graphs graphs whose vertices k element subsets dots infinite cardinal kappa k sets dots dots joined cdots k determined chromatic number these graphs paper extend definition study chromatic number graphs defined similarly other types mutual position respect underlying ordering consequence result existence graph interesting disparity chromatic behavior finite infinite subgraphs cardinal kappa integer there exists graph chi kappa finite subgraph subset chi leq log where log l iterated logarithm answers question raised erd hajnal shelah