Constructive bounds for a Ramsey-type problem

DOI10.1007/BF03352998zbMath0890.05050OpenAlexW2015922523MaRDI QIDQ1376057

Noga Alon, Michael Krivelevich

Publication date: 22 June 1998

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

finite geometriesRamsey numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of finite geometries (05B25) Generalized Ramsey theory (05C55)

Related Items (31)

Almost orthogonal subsets of vector spaces over finite fields ⋮ A clique-free pseudorandom subgraph of the pseudo polarity graph ⋮ On the Extremal Number of Subdivisions ⋮ The sovability of norm, bilinear and quadratic equations over finite fields via spectra of graphs ⋮ On the Ramsey-Turán number with small \(s\)-independence number ⋮ Bounding Ramsey numbers through large deviation inequalities ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ On point-line incidences in vector spaces over finite fields ⋮ A note on pseudorandom Ramsey graphs ⋮ The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields ⋮ A construction for clique-free pseudorandom graphs ⋮ On generalized Ramsey numbers of Erdős and Rogers ⋮ Lower bounds for multicolor Ramsey numbers ⋮ On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers ⋮ Singular matrices with restricted rows in vector spaces over finite fields ⋮ Lovász, Vectors, Graphs and Codes ⋮ Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture ⋮ Topological Bounds for Graph Representations over Any Field ⋮ An improvement on the number of simplices in \(\mathbb{F}_q^d\) ⋮ \(K_4\)-free graphs without large induced triangle-free subgraphs ⋮ Short Proofs of Some Extremal Results ⋮ Constructive lower bounds for off-diagonal Ramsey numbers ⋮ New strongly regular graphs from finite geometries via switching ⋮ Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems ⋮ Additive patterns in multiplicative subgroups ⋮ Dependent random choice ⋮ Graphs associated with orthogonal collections of \(k\)-planes over finite fields ⋮ On the spectrum of projective norm-graphs ⋮ A generalization of Turán's theorem ⋮ On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs ⋮ Approximately strongly regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Explicit construction of linear sized tolerant networks
• Intersection theorems with geometric consequences
• Graphs without large triangle free subgraphs
• A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\)
• An asymptotic isoperimetric inequality
• Explicit Ramsey graphs and orthonormal labelings
• Tough Ramsey graphs without short cycles
• Concentration of measure and isoperimetric inequalities in product spaces
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Bounding Ramsey numbers through large deviation inequalities
• On the construction of certain graphs
• On a combinatorial conjecture of Erdös
• The Construction of Certain Graphs

This page was built for publication: Constructive bounds for a Ramsey-type problem