Alphabeta Math

The Erdős–Hajnal Property and Homogeneous Sets

About this page
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 11 results · all verified · 6 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 5 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Combinatorics
Linear Algebra
Real Analysis
Set Theory
Topology
2 · Logical flowchart

3 · Items

Definition

Homogeneous vertex sets and the homogeneous number hom(G)=max{ω(G),α(G)}

Definition

The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class

Lemma

Every smaller positive exponent is again an Erdős–Hajnal constant

Theorem

Every nonempty n-vertex graph satisfies hom(G)≥ 1/2 log₂ n

Theorem

For every t≥1, the class of Kₜ-free graphs has the Erdős–Hajnal property

Theorem

Every P₃-free graph G satisfies hom(G)≥√|V(G)|

Theorem

For every n≥16 there is an n-vertex graph with hom(G)<3 log₂ n

Corollary

The hereditary class of all finite graphs does not have the Erdős–Hajnal property

Proposition

A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants

Corollary

Every graph on at most three vertices has the Erdős–Hajnal property

Proposition

The Erdős–Hajnal property and each of its constants pass to hereditary subclasses

Proposition

If H is an induced subgraph of H' and H' has the Erdős–Hajnal property, then H has it with every constant of H'

Theorem

The single-forbidden-graph and finite-nonempty-family formulations of the Erdős–Hajnal conjecture are equivalent

Remark

The Erdős–Hajnal conjecture: every fixed forbidden induced graph admits a positive exponent

Sources