On Turan's theorem for sparse graphs

DOI10.1007/BF02579451MaRDI QIDQ1167183zbMATH OpenOpenAlexWikidataFDO

Authors Miklós Ajtai, János Komlós, P. Erdős, Endre Szemerédi

Publication date 1981

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579451

zbMATH Keywords

cliqueindependent setrandom graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99) Combinatorial probability (60C05)

Review text

Let \(\alpha\) be the (vertex) independence number and let \(\log x=\max\{1,\ell nx\}\). Denote by \(f(n,t,p)\) the largest integer such that every graph of order \(n\) and average degree \(t\geq 1\) that contains no \(K_p\) satisfies \(\alpha\geq f(n,t,p)\). Theorem: There exists an absolute constant \(c_1\) such that \(f(n,t,p)>c_1\cdot(n/t)\cdot\log(\log t)/p\). This improves on the known bounds \(\alpha\geq n/(t+1)\) and \(\alpha>0.01(n/t)\log t\). The lasr inequality may be rewritten as \(f(n,t,3)>c\cdot(n/t)\log t\), and suggests the study of the question \(f(n,t,p)=c_p(n/t)\log t\).

Recommendations

• On the independence number of sparse graphs
• Turán-Ramsey Theorems and K_p-Independence Numbers
• Independence numbers of locally sparse graphs and a Ramsey type problem
• New results on \(k\)-independence of graphs
• Independence numbers of hypergraphs with sparse neighborhoods.

Cites work

• A note on Ramsey numbers
• Turan's theorem for k-graphs

Cited in

(35)

• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Independent sets in graphs with triangles
• Improved approximations for maximum independent set via approximation chains
• Independence numbers of hypergraphs with sparse neighborhoods.
• The list chromatic number of graphs with small clique number
• Retracted: A remark on the weak Turán's theorem
• Sparse hypergraphs with low independence number
• Independence and matching number of some graphs
• Stable sets in flag spheres
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• List coloring triangle-free hypergraphs
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• On vertex independence number of uniform hypergraphs
• An undecidability result on limits of sparse graphs
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• On uncrowded hypergraphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On the independence number of sparse graphs
• On constant time approximation of parameters of bounded degree graphs
• On the max min vertex cover problem
• Improved approximations of independent sets in bounded-degree graphs
• Counting Independent Sets in Hypergraphs
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• Independent sets in hypergraphs omitting an intersection
• Graph and hypergraph colouring via nibble methods: a survey
• Stable sets in flag spheres
• Independence in connected graphs
• Packing list‐colorings
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Random independent sets in triangle-free graphs
• Coloring simple hypergraphs
• Interpolating between bounds on the independence number

This page was built for publication: On Turan's theorem for sparse graphs

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