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

DOI10.1090/PROC/13626zbMATH Open1477.03131arXiv1504.08252OpenAlexW2963198117MaRDI QIDQ4596007FDOQ4596007

Authors: Artem Chernikov, S. Starchenko 

Publication date: 8 December 2017

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

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.

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

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

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)

Cites Work

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

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
• Stable formulas in ordered structures
• A remark on the stability of saturated generic graphs
• Transducing paths in graph classes with unbounded shrubdepth
• A Gallai’s Theorem type result for the edge stability of graphs
• Ramsey growth in some NIP structures
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity

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)