← All problems

Erdős Problem #576 — Turán numbers of hypercubes

62 years old · traced to

For a positive integer kk, let QkQ_k be the graph with vertex set {0,1}k\{0,1\}^k, with two vertices adjacent if they differ in exactly one coordinate. Thus QkQ_k has 2k2^k vertices and k2k−1k2^{k-1} edges. For a positive integer nn, define ex(n;Qk)\mathrm{ex}(n;Q_k) as the maximum number of edges in a simple graph on nn vertices that contains no subgraph isomorphic to QkQ_k; the forbidden copy is not required to be induced. The question is to determine, for each fixed kk, the asymptotic behaviour as n→∞n\to\infty of

ex(n;Qk).\mathrm{ex}(n;Q_k).

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 Q3Q_3, Erdős and Simonovits obtained a lower bound of order n3/2n^{3/2} and an upper bound of order n8/5n^{8/5}. Erdős had initially conjectured a lower bound of order n5/3n^{5/3}, and later asked whether the upper-bound exponent 8/58/5 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 kk on one side has extremal number O(n2−1/k)O(n^{2-1/k}). Sudakov and Tomon sharpened this to a little-oh bound when the forbidden bipartite graph is also Kk,kK_{k,k}-free. For k≥3k\geq3, 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

Progress summary

Never refreshed

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.