Rh. Schelp et A. Thomason, On quadrilaterals in layers of the cube and extremal problems for directedand oriented graphs, J GRAPH TH, 33(2), 2000, pp. 66-82
Erdos has conjectured that every subgraph of the n-cube Q(n) having more th
an (1/2+ o(1))e(Q(n)) edges will contain a 4-cycle. In this note we conside
r 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of s
izes k - 1, k and k + 1, where we are thinking of the vertices of Q(n) as b
eing the power set of {1,..., n}. Observe that every 4-cycle in Q(n) lies i
n some layer graph. We investigate the maximum density of 4-cycle free subg
raphs of layer graphs, principally the case k = 2. The questions that arise
in this case are equivalent to natural questions in the extremal theory of
directed and undirected graphs. (C) 2000 John Wiley & Sons, Inc.