Erdős Problem #576 — Turán numbers of hypercubes
For a positive integer , let be the graph with vertex set , with two vertices adjacent if they differ in exactly one coordinate. Thus has vertices and edges. For a positive integer , define as the maximum number of edges in a simple graph on vertices that contains no subgraph isomorphic to ; the forbidden copy is not required to be induced. The question is to determine, for each fixed , the asymptotic behaviour as of
Erdős Problem #576 On the Turán number of the hypercube
Background
Erdős posed the problem in 1964 for the three-dimensional cube and higher-dimensional cubes. The problem is part of extremal graph theory for bipartite forbidden graphs, where the Erdős–Stone–Simonovits theorem does not supply the leading asymptotic scale. For , Erdős and Simonovits obtained a lower bound of order and an upper bound of order . Erdős had initially conjectured a lower bound of order , and later asked whether the upper-bound exponent gives the correct order. Erdős Problem #576 On the Turán number of the hypercube
A general upper-bound benchmark follows from the maximum-degree condition: a bipartite graph with maximum degree at most on one side has extremal number . Sudakov and Tomon sharpened this to a little-oh bound when the forbidden bipartite graph is also -free. For , the cube satisfies these conditions. The stronger cube-specific estimate below uses additional structure, and the paper also gives power improvements for a broader class of graphs. On the Turán number of the hypercube Erdős Problem #576
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.