Mathematics – Combinatorics
Scientific paper
2009-06-19
Mathematics
Combinatorics
23 pages
Scientific paper
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 \d\G of a collection \G of ordered graphs, and prove the following, simple-sounding statement: if n \in \N is sufficiently large, |V(G)| = n for each G \in \G, and |\G| < n, then |\d \G| \ge |\G|. As a consequence, we substantially strengthen a result of Balogh, Bollob\'as and Morris on hereditary properties of ordered graphs: we show that if \P is such a property, and |\P_k| < k for some sufficiently large k \in \N, then |\P_n| is decreasing for k \le n < \infty.
Bollobas Bela
Brightwell Graham
Morris Robert
No associations
LandOfFree
Shadows of ordered graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shadows of ordered graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shadows of ordered graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-402168