A note on the Erdős-Hajnal property for stable graphs

DOI10.1090/PROC/13626MaRDI QIDQ4596007zbMATH OpenOpenAlexFDO

Authors Artem Chernikov, S. Starchenko

Publication date 8 December 2017

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.08252

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Classification theory, stability, and related concepts in model theory (03C45)

Abstract: In this short note we provide a relatively simple proof of the ErdH{o}s-Hajnal conjecture for families of finite (hyper-)graphs without the $k$-order property. It was originally proved by M. Malliaris and S. Shelah in "Regularity lemmas for stable graphs", Transactions AMS, 366, 2014, 1551-1585.

Recommendations

• The Erdős-Hajnal conjecture. A survey
• Erdős–Hajnal for graphs with no 5‐hole
• Erdös–Hajnal conjecture for new infinite families of tournaments
• Almost all \(H\)-free graphs have the Erdős-Hajnal property
• The Erdős-Hajnal conjecture for paths and antipaths

Cites work

• Classification theory and the number of non-isomorphic models.
• Induced Ramsey-type theorems
• On pseudo-finite dimensions
• Ramsey-type theorems
• Regularity lemma for distal structures
• Regularity lemmas for stable graphs
• The Erdős-Hajnal conjecture. A survey

Cited in

(9)

• Stability of the Haagerup property under graph products
• On 3‐graphs with no four vertices spanning exactly two edges
• Ramsey properties of algebraic graphs and hypergraphs
• A remark on the stability of saturated generic graphs
• Stable formulas in ordered structures
• Transducing paths in graph classes with unbounded shrubdepth
• A Gallai’s Theorem type result for the edge stability of graphs
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Ramsey growth in some NIP structures

This page was built for publication: A note on the Erdős-Hajnal property for stable graphs

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