On the number of containments in P-free families

DOI10.1007/S00373-019-02094-3MaRDI QIDQ2287744zbMATH OpenOpenAlexWikidataFDO

Authors Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Balázs Patkós, Máté Vizer

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1804.01606

zbMATH Keywords

comparable pairsforbidden subposet problemsset systems

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal problems in graph theory (05C35) Extremal set theory (05D05) Combinatorics of partially ordered sets (06A07)

Abstract: A subfamily $F_1,F_2,dots,F_{|P|}subseteqmathcalF$ is a copy of the poset $P$ if there exists a bijection $i:Pightarrow{F}_1,F_2,dots,F_{|P|}$ such that $pl{e}_{P}q$ implies $i(p)subseteqi(q)$. A family $mathcalF$ is $P$-free, if it does not contain a copy of $P$. In this paper we establish basic results on the maximum possible number of $k$-chains in a $P$-free family $mathcalFsubseteq{2}^{[n]}$. We prove that if the height of $P$, $h(P)>k$, then this number is of the order $$, where $l_0=n$ and $l_{1}ge{l}_{2}gedotsge{l}_{k+1}$ are such that $n-l_1,l_1-l_2,dots,l_k-l_{k+1},l_{k+1}$ differ by at most one. On the other hand if $h(P)lek$, then we show that this number is of smaller order of magnitude. Let $ve{e}_r$ denote the poset on $r+1$ elements $a,b_1,b_2,ldots,b_r$, where $a<b_i$ for all $1leiler$ and let $wedg{e}_r$ denote its dual. For any values of $k$ and $l$, we construct a $wedg{e}_k,ve{e}_l$-free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of $k$ and $l$. We also derive the asymptotics of the maximum number of copies of certain tree posets $T$ of height 2 in $wedg{e}_k,ve{e}_l$-free families $mathcalFsubseteq{2}^{[n]}$.

Recommendations

• Set families with forbidden subposets
• Generalized forbidden subposet problems
• On families of subsets with a forbidden subposet
• Supersaturation, counting, and randomness in forbidden subposet problems
• Diamond-free families

Cites work

• l-Chain Profile Vectors
• Generalized forbidden subposet problems
• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• Lower bounds for constant weight codes
• On a lemma of Littlewood and Offord
• Set families with a forbidden subposet
• The distance of \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \
• Two applications (for search theory and truth functions) of Sperner type theorems

Cited in

(12)

• Degrees of freedom versus dimension for containment orders
• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• A note on the size of \(\mathscr{N}\)-free families
• On forbidden poset problems in the linear lattice
• Intersecting P-free families
• On crown-free families of subsets
• On Generalized Turán Results in Height Two Posets
• The covering lemma and q-analogues of extremal set theory problems
• On some extremal and probabilistic questions for tree posets
• Chain-dependent conditions in extremal set theory
• Intersecting V-free, -free families
• Generalized forbidden subposet problems

This page was built for publication: On the number of containments in \(P\)-free families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287744)