Shadows of ordered graphs

摘要

Isoperimetric inequalities have been studied since antiquity, and in recent decades they have been studied extensively on discrete objects, such as the hypercube. An important special case of this problem involves bounding the size of the shadow of a set system, and the basic question was solved by Kruskal (in 1963) and Katona (in 1968). In this paper we introduce the concept of the shadow ?G of a collection G of ordered graphs, and prove the following, simple-sounding statement: if n∈N is sufficiently large, |V(G)|=n for each G∈G, and |G|