A note on multicolour Erdős-Hajnal conjecture

2023/11/06 by Maria Axenovich, Axenovich, Maria, Lea Weber +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2311.03249

openalex publication_date 2023/11/06 · openalex created_date 2023/11/08 · openalex updated_date 2026/07/28

Abstract

Informally, the Erdős-Hajnal conjecture (shortly EH-conjecture) asserts that if a sufficiently large host clique on n vertices is edge-coloured avoiding a copy of some fixed edge-coloured clique, then there is a large homogeneous set of size n^β for some positive β, where a set of vertices is homogeneous if it does not induce all the colours. This conjecture, if true, claims that imposing local conditions on edge-partitions of cliques results in a global structural consequence such as a large homogeneous set, a set avoiding all edges of some part. While this conjecture attracted a lot of attention, it is still open even for two colours. In this note, we reduce the multicolour EH-conjecture to the case when the number of colours used in a host clique is either the same as in the forbidden pattern or one more. We exhibit a non-monotonicity behaviour of homogeneous sets in coloured cliques with forbidden patterns by showing that allowing an extra colour in the host graph could actually decrease the size of a largest homogeneous set.

Related

• The Erdős-Hajnal conjecture for three colors and multiple forbidden patterns
• Large cliques or co-cliques in hypergraphs with forbidden order-size pairs
• Homogeneous sets in hypergraphs with forbidden order-size pairs
• A framework for the generalised Erdős-Rothschild problem and a resolution of the dichromatic triangle case
• Two Erdos-Hajnal-type theorems for forbidden order-size pairs