Independent sets in subgraphs of a shift graph

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Abstract: ErdH{o}s, Hajnal and Szemer'{e}di proved that any subset

G

of vertices of a shift graph

e x t {S h}_{n}^{k}

has the property that the independence number of the subgraph induced by

G

satisfies

a l p h a (e x t {S h}_{n}^{k} [G]) g e q l e f t (f r a c 12 - v a r e p s i l o n i g h t) | G |

, where

v a r e p s i l o n o 0

as

k o i n f t y

. In this note we prove that for

k = 2

and

n o i n f t y

there are graphs

with

a l p h a (e x t {S h}_{n}^{2} [G]) l e q l e f t (f r a c 14 + o (1) i g h t) | G |

, and

f r a c 14

is best possible. We also consider a related problem for infinite shift graphs.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Independent sets in subgraphs of a shift graph