Shadows of ordered graphs
From MaRDI portal
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 dG 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 3557819 (Why is no real title available?)
- scientific article; zbMATH DE number 1504588 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- A Kruskal-Katona type theorem for graphs
- A Kruskal-Katona type theorem for the linear lattice
- A jump to the Bell number for hereditary graph properties
- A note on the edges of the n-cube
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- Boolean functions with low average sensitivity depend on few coordinates
- Compressions and isoperimetric inequalities
- Concentration of measure and isoperimetric inequalities in product spaces
- Every monotone graph property has a sharp threshold
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Excluding Induced Subgraphs III: A General Asymptotic
- Extremal problems for finite sets and convex hulls---a survey
- Forbidden induced partial orders
- Forbidden paths and cycles in ordered graphs and matrices
- Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
- Hereditary properties of ordered graphs
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
- Hereditary properties of words
- Influences in Product Spaces: KKL and BKKKL Revisited
- Kruskal-Katona type theorems for clique complexes arising from chordal and strongly chordal graphs
- Nonexistence of a Kruskal-Katona type theorem for subword orders
- On boundaries and influences
- On growth rates of permutations, set partitions, ordered graphs and other objects
- On the entropy values of hereditary classes of graphs
- On the size of hereditary classes of graphs
- Optimal Assignments of Numbers to Vertices
- Optimal numberings and isoperimetric problems on graphs
- Percolation on finite graphs and isoperimetric inequalities.
- Projections of Bodies and Hereditary Properties of Hypergraphs
- Shadows and intersections: Stability and new proofs
- Shadows of colored complexes.
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The influence of variables in product spaces
- The isoperimetric inequality
- The number of graphs without forbidden subgraphs
- The speed of hereditary properties of graphs
- The structure of almost all graphs in a hereditary property
- Threshold functions
This page was built for publication: Shadows of ordered graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431242)
