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.)

chromatic number finite bipartite graphs subgraphs of large graphs

Infinite graphs (05C63) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Review text

Summary: \textit{P. Erdős} et al. [Ann. Discrete Math. 12, 117--123 (1982; Zbl 0501.05033)] proved that any subset \(G\) of vertices of a shift graph \(\text{Sh}_n^k\) has the property that the independence number of the subgraph induced by \(G\) satisfies \(\alpha(\text{Sh}_n^k[G])\geqslant \left(\frac{1}{2}-\varepsilon\right)|G|\), where \(\varepsilon\to 0\) as \(k\to \infty \). In this note we prove that for \(k=2\) and \(n \to \infty\) there are graphs \(G\subseteq \binom{[n]}{2}\) with \(\alpha(\text{Sh}_n^2[G])\leqslant \left(\frac{1}{4}+o(1)\right)|G|\), and \(\frac{1}{4}\) is best possible. We also consider a related problem for infinite shift graphs.

Recommendations

Cites work

Cited in

(2)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2121753)