A note on Ramsey numbers
From MaRDI portal
Publication:1149967
DOI10.1016/0097-3165(80)90030-8zbMath0455.05045OpenAlexW2074920973WikidataQ54278840 ScholiaQ54278840MaRDI QIDQ1149967
János Komlós, Endre Szemerédi, Miklós Ajtai
Publication date: 1980
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(80)90030-8
Related Items
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies, On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles, List coloring triangle-free hypergraphs, Improved approximations of independent sets in bounded-degree graphs, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Local Clique Covering of Claw-Free Graphs, SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY, The $\chi$-Ramsey Problem for Triangle-Free Graphs, On the Lovász Theta Function for Independent Sets in Sparse Graphs, A note on the Erdős-Hajnal hypergraph Ramsey problem, Counterexamples to a Conjecture of Harris on Hall Ratio, Around the log-rank conjecture, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Independent sets in hypergraphs omitting an intersection, On the average size of independent sets in triangle-free graphs, Edge clique covers in graphs with independence number two, On Brooks' Theorem for Sparse Graphs, Dynamic concentration of the triangle‐free process, Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth, Down‐set thresholds, Hypergraph Ramsey numbers of cliques versus stars, Rainbow independent sets in certain classes of graphs, Graph and hypergraph colouring via nibble methods: a survey, Off-diagonal book Ramsey numbers, A proof of the Erdős-Faber-Lovász conjecture, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), On Ramsey Size-Linear Graphs and Related Questions, Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs, Ramsey properties of semilinear graphs, Unnamed Item, Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs, A note on pseudorandom Ramsey graphs, The asymptotics of \(r(4,t)\), Ramsey-Turán problems with small independence numbers, Clique covers of \(H\)-free graphs, Unnamed Item, Improved Bounds for the Ramsey Number of Tight Cycles Versus Cliques, Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability, ON THE HARD SPHERE MODEL AND SPHERE PACKINGS IN HIGH DIMENSIONS, Triangle-free subgraphs with large fractional chromatic number, Ordered Ramsey numbers, Colouring Squares of Claw-free Graphs, Online Ramsey Numbers and the Subgraph Query Problem, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers, Turán and Ramsey Properties of Subcube Intersection Graphs, Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections, Coloring graphs with fixed genus and girth, Strong Turán stability, On independent sets in hypergraphs, Hypergraph Ramsey numbers, Approximating maximum independent sets by excluding subgraphs, On uncrowded hypergraphs, Bounding the Size of an Almost-Equidistant Set in Euclidean Space, Short proofs of some extremal results III, Ramsey, Paper, Scissors, Separation Choosability and Dense Bipartite Induced Subgraphs, Fraïssé structures and a conjecture of Furstenberg, Improved Ramsey-type results for comparability graphs, The Ramsey number of the clique and the hypercube, Hasse diagrams with large chromatic number, Ramsey Numbers for Nontrivial Berge Cycles, Constructing colorings for diagrams, A note on multicolor Ramsey number of small odd cycles versus a large clique, Independence in uniform linear triangle-free hypergraphs, On induced subgraphs with odd degrees, A fast network-decomposition algorithm and its applications to constant-time distributed computation, On the minimum degree of minimal Ramsey graphs for multiple colours, Almost orthogonal subsets of vector spaces over finite fields, Large induced degenerate subgraphs, What can we hope to accomplish in generalized Ramsey theory ?, Some combinatorial-algebraic problems from complexity theory, Tough Ramsey graphs without short cycles, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, The independent neighborhoods process, Independent sets in graphs with triangles, A note on the uniformity threshold for Berge hypergraphs, On Subgraphs of Bounded Degeneracy in Hypergraphs, The independence numbers of weighted graphs with forbidden cycles, Counting independent sets in triangle-free graphs, Ramsey-type results for semi-algebraic relations, On the Ramsey number \(r(H+\overline{K_ n},K_ n)\), Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs, Off-diagonal hypergraph Ramsey numbers, Disjoint cycles in graphs with restricted independence number, Covering and independence in triangle structures, Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques, Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable, Large chromatic number and Ramsey graphs, Almost-equidistant sets, The Erdős-Hajnal hypergraph Ramsey problem, Lower Bounds for On-line Graph Colorings, An improved bound for the stepping-up lemma, Packing nearly optimal Ramsey \(R(3,t)\) graphs, Off-diagonal ordered Ramsey numbers of matchings, Independence number of graphs with a prescribed number of cliques, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, On graphs with a large chromatic number that contain no small odd cycles, On vertex independence number of uniform hypergraphs, Independence in connected graphs, Colouring squares of claw-free graphs, Semi-algebraic Ramsey numbers, Independence and matching number of some graphs, Local and global colorability of graphs, A few remarks on Ramsey--Turán-type problems, Ramsey numbers of \(K_3\) and \(K_{n,n}\), Independent sets and matchings in subcubic graphs, A note concerning paths and independence number in digraphs, The bipartite \(K_{2,2}\)-free process and bipartite Ramsey number \(b(2, t)\), Some remarks on vertex Folkman numbers for hypergraphs, Extremal uncrowded hypergraphs, On Turan's theorem for sparse graphs, Substitution and \(\chi\)-boundedness, On the Ramsey numbers R(3,8) and R(3,9), Independence numbers of hypergraphs with sparse neighborhoods., On degree sums of a triangle-free graph, New bounds on the Ramsey number \(r ( I_m , L_n )\), Lovász, Vectors, Graphs and Codes, Lower bounds for independence numbers of some locally sparse graphs, Independent sets in the union of two Hamiltonian cycles, A note on the independence number of triangle-free graphs. II, Two results on Ramsey-Turán theory, Independent sets in graphs, Cycles in triangle-free graphs of large chromatic number, New bounds on the field size for maximally recoverable codes instantiating grid-like topologies, Almost all graphs with high girth and suitable density have high chromatic number, Approximating maximum independent sets by excluding subgraphs, On small graphs with highly imperfect powers, Covering the cliques of a graph with vertices, Bounding the independence number in some \((n,k,\ell,\lambda)\)-hypergraphs, Triangle-free graphs whose independence number equals the degree, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, On the existence of \(k\)-partite or \(K_p\)-free total domination edge-critical graphs, Remarks on generic stability in independent theories, Interpolating between bounds on the independence number, A note on Ramsey size-linear graphs, Large induced forests in sparse graphs, The early evolution of the \(H\)-free process, A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs, Hypergraph Ramsey numbers: tight cycles versus cliques, Saturation problems in the Ramsey theory of graphs, posets and point sets, Structure and colour in triangle-free graphs, Large induced trees in \(K_r\)-free graphs, Multicolor Ramsey numbers via pseudorandom graphs, A Ramsey-type result for geometric \(\ell\)-hypergraphs, List-coloring claw-free graphs with small clique number, The triangle-free process, Revisiting a theorem by Folkman on graph colouring, Ramsey numbers and an approximation algorithm for the vertex cover problem, On the independence number of non-uniform uncrowded hypergraphs, Lower bounds on the independence number in terms of the degrees, New theoretical bounds and constructions of permutation codes under block permutation metric, An upper bound on the Ramsey numbers R(3,k), Some Results on Chromatic Number as a Function of Triangle Count, A note on the independence number of triangle-free graphs, Fragmentability of graphs, Chromatic number of finite and infinite graphs and hypergraphs, Randomly finding independent sets in locally sparse graphs, On off-diagonal ordered Ramsey numbers of nested matchings, Phase transitions in Ramsey-Turán theory, Approximately strongly regular graphs, The Erdős-Hajnal conjecture for three colors and triangles
Cites Work
