{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:51Z","timestamp":1753893831844,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Erd\u0151s, Hajnal and Szemer\u00e9di 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])\\geq \\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])\\leq \\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.<\/jats:p>","DOI":"10.37236\/10453","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:56Z","timestamp":1645705196000},"source":"Crossref","is-referenced-by-count":0,"title":["Independent Sets in Subgraphs of a Shift Graph"],"prefix":"10.37236","volume":"29","author":[{"given":"Andrii","family":"Arman","sequence":"first","affiliation":[]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[]},{"given":"Marcelo Tadeu","family":"Sales","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2022,2,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p26\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p26\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T12:19:56Z","timestamp":1645705196000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i1p26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.37236\/10453","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,2,11]]},"article-number":"P1.26"}}