Search for: All records

Abstract A well‐known result of Ajtai Komlós, Pintz, Spencer, and Szemerédi (J. Combin. Theory Ser. A32(1982), 321–335) states that every ‐graph on vertices, with girth at least five, and average degree contains an independent set of size for some . In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3, and 4. Our work is motivated by a problem of Lo and Zhao, who asked for , how large of an independent set a ‐graph on vertices necessarily has when its maximum ‐degree . (The corresponding problem with respect to ‐degrees was solved by Kostochka, Mubayi, and Verstraëte (Random Struct. & Algorithms44(2014), 224–239).) In this paper we show that every ‐graph on vertices with contains an independent set of size , and under additional conditions, an independent set of size . The former assertion gives a new upper bound for the ‐degree Turán density of complete ‐graphs.