Erdős problem 1036 · problems.science

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1036.lean

Retained formal statement2 of 3

Alon and Hajnal [AlHa91] proved that $G$ must contain at least $\exp\left(n(\log n)^{-O(\log\log n)}\right)$ many non-isomorphic induced subgraphs.

FormalConjectures/ErdosProblems/1036.leanErdos1036.erdos_1036.variants.alon_hajnal10 linesExact file

1∀ (c : ℝ),2  0 < c →3    ∃ C,4      0 < C ∧5        ∀ᶠ (n : ℕ) in Filter.atTop,6          ∀ (G : SimpleGraph (Fin n)),7            ↑G.cliqueNum ≤ c * Real.log ↑n →8              ↑G.indepNum ≤ c * Real.log ↑n →9                Erdos1036.HasManyNonIsomorphicInducedSubgraphs G10                  (Real.exp (↑n * Real.log ↑n ^ (-(C * Real.log (Real.log ↑n)))))

SolvedStatement only, no proof

Sources

Search problems.science