Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-07T01:04:58.271Z Has data issue: false hasContentIssue false
  • English
  • Français

Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

Published online by Cambridge University Press:  15 February 2017

ABHISHEK METHUKU  and
DÖMÖTÖR PÁLVÖLGYI
ABHISHEK METHUKU
Affiliation:
Department of Mathematics, Central European University, 1051 Budapest, Hungary (e-mail: abhishekmethuku@gmail.com)
DÖMÖTÖR PÁLVÖLGYI
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WA, UK (e-mail: dom@cs.elte.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove that for every poset P, there is a constant CP such that the size of any family of subsets of {1, 2, . . ., n} that does not contain P as an induced subposet is at most

$$C_P{\binom{n}{\lfloor\gfrac{n}{2}\rfloor}},$$
settling a conjecture of Katona, and Lu and Milans. We obtain this bound by establishing a connection to the theory of forbidden submatrices and then applying a higher-dimensional variant of the Marcus–Tardos theorem, proved by Klazar and Marcus. We also give a new proof of their result.

Keywords

Primary 05D05Secondary 05A05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 593 - 602
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Boehnlein, E. and Jiang, T. (2012) Set families with a forbidden induced subposet. Combin. Probab. Comput. 21 496–511.Google Scholar
[2] Bukh, B. (2009) Set families with a forbidden subposet. Electron. J. Combin. 16 R142.Google Scholar
[3] Burcsi, P. and Nagy, D. T. (2013) The method of double chains for largest families with excluded subposet. Electron. J. Graph Theory Appl. 1 40–49.Google Scholar
[4] Carroll, T. and Katona, G. O. H. (2008) Bounds on maximal families of sets not containing three sets with A ∪ B ⊂ C, A ¬ ⊂ B. Order 25 229–236.Google Scholar
[5] Chen, H. B. and Li, W.-T. (2014) A note on the largest size of families of sets with a forbidden poset. Order 31 137–142.CrossRefGoogle Scholar
[6] Erdős, P. (1945) On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51 898–902.CrossRefGoogle Scholar
[7] Fox, J. (2013) Stanley–Wilf limits are typically exponential. arXiv:1310.8378 Google Scholar
[8] Füredi, Z. and Hajnal, P. (1992) Davenport–Schinzel theory of matrices. Discrete Math. 103 233–251.Google Scholar
[9] Geneson, J. T. and Tian, P. M. (2015) Extremal functions of forbidden multidimensional matrices. arXiv:1506.03874 Google Scholar
[10] Griggs, J. R. and Li, W.-T. (2016) Progress on poset-free families of subsets. In Recent Trends in Combinatorics (Beveridge, A. et al., eds), Springer, pp. 317–338.Google Scholar
[11] Griggs, J. R., Li, W.-T. and Lu, L. (2012) Diamond-free families. J. Combin. Theory. Ser. A 119 310–322.Google Scholar
[12] Griggs, J. R. and Lu, L. (2009) On families of subsets with a forbidden subposet. Combin. Probab. Comput. 18 731–748.Google Scholar
[13] Grósz, D., Methuku, A. and Tompkins, C. (2014) An improvement of the general bound on the largest family of subsets avoiding a subposet. Order, pp. 1–13.Google Scholar
[14] Grósz, D., Methuku, A. and Tompkins, C. (2016) An upper bound on the size of diamond-free families of sets. arXiv:1601.06332 Google Scholar
[15] Katona, G. O. H. (1972) A simple proof of the Erdős–Chao Ko–Rado theorem. J. Combin. Theory. Ser. B 13 183–184.Google Scholar
[16] Katona, G. O. H. (2008) Forbidden intersection patterns in the families of subsets (introducing a method). In Horizons of Combinatorics (Győri, E., Katona, G. and Lovász, L., eds), Springer, pp. 119–140.Google Scholar
[17] Katona, G. O. H. (2012) Personal communication.Google Scholar
[18] Katona, G. O. H. and Tarján, T. G. (1983) Extremal problems with excluded subgraphs in the n-cube. In Graph Theory (Borowiecki, M., Kennedy, J. W. and Sysło, M. M., eds), Springer, pp. 84–93.Google Scholar
[19] Klazar, M. and Marcus, A. (2006) Extensions of the linear bound in the Füredi–Hajnal conjecture. Adv. Appl. Math. 38 258–266.Google Scholar
[20] Loomis, H. L. and Whitney, H. (1949) An inequality related to the isoperimetric inequality. Bull. Amer. Math. Soc. 55 961–962.Google Scholar
[21] Lu, L. and Milans, K. G. (2015) Set families with forbidden subposets. Journal of Combinatorial Theory, Series A 136 126–142.Google Scholar
[22] Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory. Ser. A 107 153–160.Google Scholar
[23] Méroueh, A. (2015) Lubell mass and induced partially ordered sets. arXiv:1506.07056 Google Scholar
[24] Patkós, B. (2015) Induced and non-induced forbidden subposet problems. Electron. J. Combin. 22 P1.30.Google Scholar
[25] Sperner, E. (1928) Ein Satz über Untermegen einer endlichen Menge. Math. Z. 27 544–548.CrossRefGoogle Scholar
[26] Tardos, G. (2005) On 0–1 matrices and small excluded submatrices. J. Combin. Theory. Ser. A 111 266–288.Google Scholar