On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
✍ Scribed by Schelp, Richard H.; Thomason, Andrew
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 286 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Erdős 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.