On a Ramsey type theorem
From MaRDI portal
Let \(\bar G\) denote the complement of the graph \(G\), and let \(K_n\) denote the complete graph on \(n\) vertices. The main result of this paper is the following: Theorem 2. Let \(G(n,r)\) be a graph of \(n\) vertices with \(r<{n^2 \over k}\) edges. Then there is a positive constant \(c\) such that for \(s<c{k \over \log k} \log n\), either \(\overline{G(n,r)}\) or \(G(n,r)\) contains \(K_s\) as a subgraph. This result is shown to be best possible as far as the order of magnitude is concerned.
Recommendations
Cites work
Cited in
(59)- Some Ramsey-type theorems
- On a Ramsey-theoretic property of orders
- On a Ramsey-Turán type problem
- Problems and results in discrete mathematics
- Non-Ramsey graphs are c n-universal
- On Erdős-Rado numbers
- Ramsey numbers of books and quasirandomness
- The oriented size Ramsey number of directed paths
- Finding unavoidable colorful patterns in multicolored graphs
- An upper bound for the restricted online Ramsey number
- Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
- Distinct degrees and homogeneous sets
- On the strength of Ramsey's theorem for pairs
- scientific article; zbMATH DE number 6378629 (Why is no real title available?)
- A parametrization of the abstract Ramsey theorem
- On a Ramsey-type problem of Erdős and Pach
- Distinct degrees in induced subgraphs
- Short proofs of some extremal results. III
- Sizes of induced subgraphs of Ramsey graphs
- Ramsey type theorems for real functions
- The size Ramsey number of a directed path
- A Ramsey-Type Theorem in the Plane
- A Ramsey-Type Result for Convex Sets
- scientific article; zbMATH DE number 1047745 (Why is no real title available?)
- On the Structure of Edge Graphs
- scientific article; zbMATH DE number 2058397 (Why is no real title available?)
- A Ramsey‐type problem and the Turán numbers*
- Induced subgraphs with many distinct degrees
- On a Ramsey-type problem of Erdős and Pach
- Ramsey theory on Steiner triples
- Large cliques and independent sets all over the place
- An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
- Complementary Ramsey numbers and Ramsey graphs
- Proof of a conjecture on induced subgraphs of Ramsey graphs
- A conjecture of Erdős on graph Ramsey numbers
- Ordered Ramsey numbers
- Induced Ramsey-type theorems
- Induced Ramsey-type theorems
- Tower Gaps in Multicolour Ramsey Numbers
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Hypergraph Ramsey numbers of cliques versus stars
- A bipartite version of the Erdős–McKay conjecture
- The (t−1) $(t-1)$‐chromatic Ramsey number for paths
- A lower bound for set‐coloring Ramsey numbers
- Ramsey numbers with prescribed rate of growth
- Ramsey numbers upon vertex deletion
- Formalizing finite Ramsey theory in Lean 4
- Graphs with arbitrary Ramsey number and connectivity
- Ordered Ramsey numbers of graphs with m edges
- On the sizes of k-subgraphs of the binomial random graph
- Tower gaps in multicolour Ramsey numbers (extended abstract)
- A lower bound for set-colouring Ramsey numbers (extended abstract)
- Chromatic Ramsey numbers and two-color Turán densities
- Ramsey-type theorems
- On the number of homogeneous subgraphs of a graph
- Extremal subgraphs for two graphs
- Edge-colored complete graphs with precisely colored subgraphs
- Induced subgraphs of Ramsey graphs with many distinct degrees
This page was built for publication: On a Ramsey type theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2553974)
