On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

摘要

Erdos has conjectured that every subgraph of the n-cube Q(n) having more than (1/2+ o(1))e(Q(n)) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k - 1, k and k + 1, where we are thinking of the vertices of Q(n) as being the power set of {1,..., n}. Observe that every 4-cycle in Q(n) lies in some layer graph. We investigate the maximum density of 4-cycle free subgraphs 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. [References: 15]