Shadows of ordered graphs

Details Shadows of ordered graphs Shadows of ordered graphs

2009-06-19

arxiv.org/abs/0906.3724v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-402168