Problem 666

Let $Q_n$ be the $n$ -dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that, for every $\epsilon>0$ , if $n$ is sufficiently large, every subgraph of $Q_n$ with

\geq \epsilon n2^{n-1}

many edges contains a $C_6$ ?

Source: erdosproblems.com/666

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN). The site answers the question with no and credits Chung [Ch92] and Brouwer, Dejter and Thomassen [BDT93] with an edge-partition of $Q_n$ into four subgraphs none containing a $C_6$ , so a class with a quarter of the edges avoids $C_6$ ; each paper is recorded as an accepted claim, on the refereed venue and the site's acceptance, on Chung's claim page (1992) and the Brouwer--Dejter--Thomassen claim page (1993), from which the frontmatter standing is derived. The site's label is "DISPROVED (LEAN)"; the formalization its Lean qualification refers to is linked on both claim pages and described under Formalization below.

BDT93: Brouwer, A. E. and Dejter, I. J. and Thomassen, C., Highly symmetric subgraphs of hypercubes. J. Algebraic Combin. 2 (1993), 25-29.
Ch92: Chung, Fan R. K., Subgraphs of a hypercube containing no small even cycles. J. Graph Theory (1992), 273-286.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406.

Problem 666

Status

Proof claims

Discussion