Shadows of ordered graphs
| Autor: | Béla Bollobás, Robert Morris, Graham Brightwell |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Ordered graph
0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics Set (abstract data type) Kruskal's algorithm Bounding overwatch FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Hereditary property Special case Mathematics Discrete mathematics 010102 general mathematics Shadow Computational Theory and Mathematics 010201 computation theory & mathematics Kruskal–Katona Combinatorics (math.CO) Hypercube Isoperimetric inequality |
| Zdroj: | Journal of Combinatorial Theory, Series A. 118(3):729-747 |
| ISSN: | 0097-3165 |
| DOI: | 10.1016/j.jcta.2010.11.018 |
| Popis: | 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��s and Morris on hereditary properties of ordered graphs: we show that if ��is such a property, and |��_k| < k for some sufficiently large k \in \N, then |��_n| is decreasing for k \le n < \infty. 23 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect