Skip to content

Erdős problem 666

Let QnQ_n be the nn-dimensional hypercube graph (so that QnQ_n has 2n2^n vertices and n2n−1n2^{n-1} edges). Is it true that, for every ϵ>0\epsilon>0, if nn is sufficiently large, every subgraph of QnQ_n with ≥ϵn2n−1\geq \epsilon n2^{n-1} many edges contains a C6C_6?

Erdős Problems records this as disproved (Lean).

No Repository has ruled on it here.

How far the record reaches4 of 6 stages
  1. Sourceerdos-problems
  2. StatementRetained
  3. Formal1 retained
  4. Resolutiondisproved (Lean)
  5. WorkNone recorded
  6. DecisionNone here
  7. The questionNot reached
What this record is missingWork

Nothing here has checked that finding.

Reproducing it here turns a report into evidence.

Where the source files it274 share a topic
None carries a Standing. Browse the topic.