Dependent random choice
From MaRDI portal
Abstract: We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them.
Recommendations
Cites work
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- A correlation inequality for bipartite graphs
- A few remarks on Ramsey--Turán-type problems
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- A statistical theorem of set addition
- An approximate version of Sidorenko's conjecture
- Bounding Ramsey numbers through large deviation inequalities
- Constructive bounds for a Ramsey-type problem
- Crossing patterns of segments
- Cube Ramsey numbers are polynomial
- Density theorems for bipartite graphs and related Ramsey-type results
- Edge-coloring cliques with three colors on all 4-cliques
- Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
- Graphs with linearly bounded Ramsey numbers
- scientific article; zbMATH DE number 3891408 (Why is no real title available?)
- scientific article; zbMATH DE number 3946178 (Why is no real title available?)
- Hypergraph packing and sparse bipartite Ramsey numbers
- Induced subgraphs of prescribed size
- Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems
- Minors in expanding graphs
- Norm-graphs: Variations and applications
- On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
- On a problem of Duke-Erdős-Rödl on cycle-connected subgraphs
- On bipartite graphs with linear Ramsey numbers
- On book-complete graph Ramsey numbers
- On Conway's thrackle conjecture
- On graphs with linear Ramsey numbers
- On graphs with small Ramsey numbers
- On graphs with small Ramsey numbers. II.
- On large intersecting subfamilies of uniform setfamilies
- On Ramsey Numbers of Sparse Graphs
- On Ramsey numbers of uniform hypergraphs with given maximum degree
- On the Littlewood Problem Modulo a Prime
- On the Ramsey number of sparse 3-graphs
- Product representations of polynomials
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Property testing and its connection to learning and approximation
- Ramsey goodness and beyond
- Ramsey numbers of sparse hypergraphs
- Ramsey-type problem for an almost monochromatic \(K_4\)
- Testing subgraphs in directed graphs
- The Construction of Certain Graphs
- The Littlewood-Gowers problem
- Unavoidable patterns
- Unavoidable subgraphs of colored graphs
Cited in
(72)- On the Ramsey-Turán numbers of graphs and hypergraphs
- On the rational Turán exponents conjecture
- \(p\)-arrangeable graphs are Folkman linear
- Tight bounds for powers of Hamilton cycles in tournaments
- On explicit constructions of designs
- Finding unavoidable colorful patterns in multicolored graphs
- Partial associativity and rough approximate groups
- More on the extremal number of subdivisions
- Two results on Ramsey-Turán theory
- On the relation of separability, bandwidth and embedding
- Subdivisions of a large clique in \(C_6\)-free graphs
- Phase transitions in Ramsey-Turán theory
- Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
- The Turán number of blow-ups of trees
- Frankl-Rödl-type theorems for codes and permutations
- Packing Hamilton cycles online
- Large unavoidable subtournaments
- Short proofs of some extremal results. II.
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Sidorenko's conjecture for blow-ups
- Short proofs of some extremal results. III
- A Folkman linear family
- On the Ramsey-Turán number with small s-independence number
- Two extensions of Ramsey's theorem
- A minimum degree condition forcing complete graph immersion
- Few products, many h-fold sums
- Two Conjectures in Ramsey--Turán Theory
- Induced Turán numbers
- A counterexample to sparse removal
- A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem
- Ramsey properties of randomly perturbed graphs: cliques and cycles
- Maker-Breaker games on randomly perturbed graphs
- Large Rainbow Cliques in Randomly Perturbed Dense Graphs
- Turán theorems for unavoidable patterns
- On the extremal number of subdivisions
- Ramsey numbers of cubes versus cliques
- The critical window for the classical Ramsey-Turán problem
- Large unavoidable subtournaments
- The Ramsey number of the clique and the hypercube
- Cycles Are Strongly Ramsey-Unsaturated
- Tree-Degenerate Graphs and Nested Dependent Random Choice
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Sets without k‐term progressions can have many shorter progressions
- The intersection spectrum of 3‐chromatic intersecting hypergraphs
- Tower-type bounds for Roth's theorem with popular differences
- Clique-factors in graphs with sublinear -independence number
- On Ramsey Size-Linear Graphs and Related Questions
- Rainbow clique subdivisions
- An approximate version of Sidorenko's conjecture
- Embedding bipartite distance graphs under Hamming metric in finite fields
- Phase transitions of structured codes of graphs
- Ramsey numbers for multiple copies of sparse graphs
- A remark on the Ramsey number of the hypercube
- Two Ramsey problems in blowups of graphs
- Unavoidable patterns in locally balanced colourings
- Spanning subdivisions in Dirac graphs
- Extremal graphs for the odd prism
- Interview with David Conlon
- Extremal density for subdivisions with length or sparsity constraints
- Counting independent sets in structured graphs
- The evolution of unavoidable bichromatic patterns and extremal cases of balanceability
- Extremal number of graphs from geometric shapes
- Two Ramsey-Turán numbers of small independence numbers
- A sharp lower bound for the number of mappings of a linear graph into an arbitrary graph and an inequality of A. F. Sidorenko
- Phase transition of degenerate Turán problems in p-norms
- Canonical Ramsey numbers of sparse graphs
- Induced Ramsey problems for trees and graphs with bounded treewidth
- Bollobás-Erdős-Tuza conjecture for graphs with no induced \(K_{s , t}\)
- Unavoidable patterns in 2-colorings of the complete bipartite graph
- Embedding clique subdivisions via crux
- An improved Turán exponent for 2-complexes
- State dependent choice
This page was built for publication: Dependent random choice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068761)
