Premium
On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
Author(s) -
Schelp Richard H.,
Thomason Andrew
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200002)33:2<66::aid-jgt2>3.0.co;2-l
Subject(s) - quadrilateral , mathematics , combinatorics , cube (algebra) , discrete mathematics , engineering , finite element method , structural engineering
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. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000