Name
Abstract | ||
|---|---|---|
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|=|G|. As a consequence, we substantially strengthen a result of Balogh, Bollobas and Morris on hereditary properties of ordered graphs: we show that if P is such a property, and |P"k| |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcta.2010.11.018 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
hereditary property,isoperimetric inequality,discrete object,ordered graph,basic question,shadow,important special case,kruskal–katona,set system,recent decade,simple-sounding statement,collection g | Discrete mathematics,Combinatorics,Hereditary property,Ordered graph,Inequality,Isoperimetric inequality,Kruskal's algorithm,Mathematics,Hypercube,Special case,Bounding overwatch | Journal |
Volume | Issue | ISSN |
118 | 3 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
0 | 0.34 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| Graham R. Brightwell | 2 | 192 | 25.09 |
| Robert Morris | 3 | 101 | 13.12 |