Erdős problem 426

We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$ . Is there a graph on $n$ vertices with $\gg \frac{2^{\binom{n}{2}}}{n!}$ many distinct unique subgraphs?

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

FormalConjectures/ErdosProblems/

426.lean

Retained formal statement2 of 2

Sanity check: the empty graph ⊥ is a unique subgraph of itself. Its only subgraph is ⊥ (everything ≤ ⊥ equals ⊥), which is isomorphic to ⊥ via the identity.

FormalConjectures/ErdosProblems/426.leanErdos426.isUniqueSubgraph_bot_bot1 lineExact file

1∀ {V : Type u_1}, ⊥.IsUniqueSubgraph ⊥

TestStatement only, no proof