Skip to content

Erdős problem 1036

Start work

Let GG be a graph on nn vertices which does not contain a trivial (empty or complete) graph on more than clog⁡nc\log n vertices. Must GG contain at least 2Ωc(n)2^{\Omega_c(n)} many induced subgraphs which are not pairwise isomorphic?

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1036.lean

Retained formal statement3 of 3

Erdős and Hajnal [ErHa89b] proved that if GG does not contain a complete bipartite graph or its complement on more than clog⁡nc\log n vertices then GG contains at least 2Ωc(n)2^{\Omega_c(n)} many non-isomorphic induced subgraphs.

FormalConjectures/ErdosProblems/1036.leanErdos1036.erdos_1036.variants.erdos_hajnal8 linesExact file
∀ (c : ℝ),  0 < c →    ∃ δ,      0 < δ ∧        ∀ᶠ (n : ℕ) in Filter.atTop,          ∀ (G : SimpleGraph (Fin n)),            Erdos1036.NoLargeInducedBipartite G (c * Real.log ↑n) →              Erdos1036.HasManyNonIsomorphicInducedSubgraphs G (2 ^ (δ * ↑n))
SolvedStatement only, no proof