×

Shadows of ordered graphs. (English) Zbl 1232.05104

Summary: 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 J. B. Kruskal [Math. Optimization Tech. 251–278 (1963; Zbl 0116.35102)] and G. O. H. Katona [Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 187-207 (1968; Zbl 0313.05003)]. In this paper we introduce the concept of the shadow \(\partial \mathcal G\) of a collection \(\mathcal G\) of ordered graphs, and prove the following, simple-sounding statement: if \(n \in \mathbb N\) is sufficiently large, |\(V(G)|=n\) for each \(G \in \mathcal G\), and \(|\mathcal G| < n\), then \(|\partial \mathcal G| \geqslant |\mathcal 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 \(\mathcal P\) is such a property, and \(|\mathcal P_k| < k\) for some sufficiently large \(k \in \mathbb N\), then \(|\mathcal P_n|\) is decreasing for \(k\leqslant n<\infty \).

MSC:

05C35 Extremal problems in graph theory
05C65 Hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
06A06 Partial orders, general
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alekseev, V. E., On the entropy values of hereditary classes of graphs, Discrete Math. Appl., 3, 191-199 (1993) · Zbl 0797.05077
[2] N. Alon, J. Balogh, B. Bollobás, R. Morris, The structure of almost all graphs in a hereditary property, J. Combin. Theory Ser. B, in press.; N. Alon, J. Balogh, B. Bollobás, R. Morris, The structure of almost all graphs in a hereditary property, J. Combin. Theory Ser. B, in press.
[3] Alon, N.; Benjamini, I.; Stacey, A., Percolation on finite graphs and isoperimetric inequalities, Ann. Probab., 32, 1727-1745 (2004) · Zbl 1046.05071
[4] Balogh, J.; Bollobás, B., Hereditary properties of words, Theor. Inform. Appl., 39, 49-65 (2005) · Zbl 1132.68048
[5] Balogh, J.; Bollobás, B.; Morris, R., Hereditary properties of ordered graphs, (Klazar, M.; Kratochvíl, J.; Loebl, M.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics. Topics in Discrete Mathematics, Algorithms Combin., vol. 26 (2006), Springer), 179-213, special edition for J. Nešetřil · Zbl 1117.05104
[6] Balogh, J.; Bollobás, B.; Morris, R., Hereditary properties of partitions, ordered graphs and ordered hypergraphs, European J. Combin., 27, 1263-1281 (2006) · Zbl 1114.05068
[7] Balogh, J.; Bollobás, B.; Simonovits, M., On the number of graphs without forbidden subgraphs, J. Combin. Theory Ser. B, 91, 1-24 (2004) · Zbl 1044.05044
[8] Balogh, J.; Bollobás, B.; Weinreich, D., The speed of hereditary properties of graphs, J. Combin. Theory Ser. B, 79, 131-156 (2000) · Zbl 1026.05062
[9] Balogh, J.; Bollobás, B.; Weinreich, D., A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B, 95, 29-48 (2005) · Zbl 1070.05052
[10] Bezrukov, S.; Blokhuis, A., A Kruskal-Katona type theorem for the linear lattice, European J. Combin., 20, 123-130 (1999) · Zbl 0929.06003
[11] Bollobás, B., Combinatorics (1986), Cambridge University Press
[12] Bollobás, B., Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring, Proceedings of the International Congress of Mathematicians, vol. III. Proceedings of the International Congress of Mathematicians, vol. III, Berlin, 1998. Proceedings of the International Congress of Mathematicians, vol. III. Proceedings of the International Congress of Mathematicians, vol. III, Berlin, 1998, Doc. Math. Extra Vol., III, 333-342 (1998), (electronic) · Zbl 0902.05028
[13] Bollobás, B.; Leader, I., Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A, 56, 47-62 (1990) · Zbl 0731.05043
[14] Bollobás, B.; Thomason, A., Threshold functions, Combinatorica, 7, 35-38 (1987) · Zbl 0648.05048
[15] Bollobás, B.; Thomason, A., Projections of bodies and hereditary properties of hypergraphs, Bull. Lond. Math. Soc., 27, 417-424 (1995) · Zbl 0836.05072
[16] Bourgain, J.; Kahn, J.; Kalai, G.; Katznelson, Y.; Linial, N., The influence of variables in product spaces, Israel J. Math., 77, 55-64 (1992) · Zbl 0771.60002
[17] Brightwell, G.; Grable, D. A.; Prömel, H. J., Forbidden induced partial orders, Discrete Math., 201, 53-90 (1999) · Zbl 0940.06003
[18] Erdős, P.; Frankl, P.; Rödl, V., The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin., 2, 113-121 (1986) · Zbl 0593.05038
[19] Erdős, P.; Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of \(K_n\)-free graphs, (Colloquio Internazionale sulle Teorie Combinatorie, vol. II. Colloquio Internazionale sulle Teorie Combinatorie, vol. II, Rome, 1973. Colloquio Internazionale sulle Teorie Combinatorie, vol. II. Colloquio Internazionale sulle Teorie Combinatorie, vol. II, Rome, 1973, Atti Convegni Lincei, vol. 17 (1976), Accad. Naz. Lincei: Accad. Naz. Lincei Rome), 19-27
[20] Frankl, P.; Füredi, Z.; Kalai, G., Shadows of colored complexes, Math. Scand., 63, 169-178 (1988) · Zbl 0651.05003
[21] Friedgut, E., Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 18, 1, 27-36 (1998) · Zbl 0909.06008
[22] Friedgut, E., Influences in product spaces, KKL and BKKKL revisited, Combin. Probab. Comput., 13, 17-29 (2004) · Zbl 1057.60007
[23] Friedgut, E.; Kalai, G., Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc., 124, 2993-3002 (1996) · Zbl 0864.05078
[24] Friedgut, E.; Kalai, G.; Naor, A., Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math., 29, 427-437 (2002) · Zbl 1039.91014
[25] Frohmader, A., A Kruskal-Katona type theorem for graphs, J. Combin. Theory Ser. A, 117, 17-37 (2010) · Zbl 1230.05174
[26] Harper, L. H., Optimal assignment of numbers to vertices, J. Soc. Ind. Appl. Math., 12, 131-135 (1964) · Zbl 0222.94004
[27] Harper, L. H., Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory, 1, 385-393 (1966) · Zbl 0158.20802
[28] Hart, S., A note on the edges of the \(n\)-cube, Discrete Math., 14, 157-163 (1976) · Zbl 0363.05058
[29] Herzog, J.; Hibi, T.; Murai, S.; Trung, N. V.; Zheng, X., Kruskal-Katona type theorems for clique complexes arising from chordal and strongly chordal graphs, Combinatorica, 28, 315-323 (2008) · Zbl 1175.05136
[30] Kahn, J.; Kalai, G.; Linial, N., The influence of variables on Boolean functions, (Proc. 29-th Ann. Symp. on Foundations of Comp. Sci. (1988), Computer Society Press), 68-80
[31] Katona, G. O.H., A theorem on finite sets, (Erdős, P.; Katona, G. O.H., Theory of Graphs (1968), Akadémiai Kiadó: Akadémiai Kiadó Budapest), 187-207 · Zbl 0878.05079
[32] Keevash, P., Shadows and intersections: stability and new proofs, Adv. Math., 218, 1685-1703 (2008) · Zbl 1160.05055
[33] Klazar, M., The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, (Krob, D.; Mikhalev, A. A.; Mikhalev, A. V., Formal Power Series and Algebraic Combinatorics (2000), Springer: Springer Berlin), 250-255 · Zbl 0954.05048
[34] Klazar, M., On growth rates of closed sets of permutations, set partitions, ordered graphs and other objects, Electron. J. Combin., 15 (2008), Research article R75, 22 pp · Zbl 1163.05308
[35] Kruskal, J. B., The number of simplices in a complex, (Mathematical Optimization Techniques (1963), Univ. California Press: Univ. California Press Berkeley), 251-278
[36] Leck, U., Nonexistence of a Kruskal-Katona type theorem for subword orders, Combinatorica, 24, 305-312 (2004) · Zbl 1058.06003
[37] Marcus, A.; Tardos, G., Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A, 107, 153-160 (2004) · Zbl 1051.05004
[38] R. O’Donnell, K. Wimmer, KKL, Kruskal-Katona, and monotone nets, in: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 725-734.; R. O’Donnell, K. Wimmer, KKL, Kruskal-Katona, and monotone nets, in: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 725-734.
[39] Osserman, R., The isoperimetric inequality, Bull. Amer. Math. Soc., 84, 1182-1238 (1978) · Zbl 0411.52006
[40] Pach, J.; Tardos, G., Forbidden paths and cycles in ordered graphs and matrices, Israel J. Math., 155, 359-380 (2006) · Zbl 1132.05035
[41] Prömel, H. J.; Steger, A., Excluding induced subgraphs III: A general asymptotic, Random Structures Algorithms, 3, 19-31 (1992) · Zbl 0751.05041
[42] Scheinerman, E. R.; Zito, J., On the size of hereditary classes of graphs, J. Combin. Theory Ser. B, 61, 16-39 (1994) · Zbl 0811.05048
[43] Steiner, J., Einfacher Beweis der isoperimetrischen Hauptsätze, J. Reine Angew. Math., 18, 281-296 (1838) · ERAM 018.0600cj
[44] Talagrand, M., On boundaries and influences, Combinatorica, 17, 275-285 (1997) · Zbl 0886.05110
[45] Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. Inst. Hautes Etudes Sci., 81, 73-203 (1995) · Zbl 0864.60013
[46] Wiegert, J., The sagacity of circles: A history of the isoperimetric problem, History of Mathematics SIGMAA 2006 Student Paper Contest Winner, see
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.