# An Improvement of the General Bound on the Largest Family of Subsets Avoiding a Subposet

@article{Grsz2017AnIO, title={An Improvement of the General Bound on the Largest Family of Subsets Avoiding a Subposet}, author={D{\'a}niel Gr{\'o}sz and Abhishek Methuku and Casey Tompkins}, journal={Order}, year={2017}, volume={34}, pages={113-125} }

Let La(n, P) be the maximum size of a family of subsets of [n] = {1, 2, … , n} not containing P as a (weak) subposet, and let h(P) be the length of a longest chain in P. The best known upper bound for La(n, P) in terms of |P| and h(P) is due to Chen and Li, who showed that La(n,P)≤1m+1|P|+12(m2+3m−2)(h(P)−1)−1n⌊n/2⌋$\text {La}(n,P) \le \frac {1}{m+1} \left (|{P}| + \frac {1}{2}(m^{2} +3m-2)(h(P)-1) -1 \right ) {\left (\begin {array}{c}{n}\\ {\lfloor n/2 \rfloor } \end {array}\right )}$ for any… Expand

#### Figures and Topics from this paper

#### 16 Citations

Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices

- Mathematics, Computer Science
- Order
- 2018

A double-chain method is elaborates to obtain a new upper bound for any graded poset P, where α(GP) denotes the independence number of an auxiliary graph defined in terms of P, which enables us to find more posets which verify an important conjecture by Griggs and Lu. Expand

On the size of the largest P-free families

- 2015

We will study the problem of determining the maximum size of a family of subsets of [n] = {1, 2, . . . , n} not containing a given poset P as a (weak) subposet, denoted La(n, P ). This problem is a… Expand

An upper bound on the size of diamond-free families of sets

- Mathematics, Computer Science
- J. Comb. Theory, Ser. A
- 2018

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet. The diamond poset, denoted $B_{2}$, is defined on four elements $x,y,z,w$ with… Expand

Progress on poset-free families of subsets

- Mathematics
- 2016

Increasing attention is being paid to the study of families of subsets of an n-set that contain no subposet P. Especially, we are interested in such families of maximum size given P and n. For… Expand

Forbidden induced subposets of given height

- Mathematics, Computer Science
- J. Comb. Theory, Ser. A
- 2019

This paper shows that a special partition of the largest family of a partially ordered set can be used to derive bounds in a number of other extremal set theoretical problems and their generalizations in grids, such as the size of families avoiding weak posets, Boolean algebras, or two distinct sets and their union. Expand

Induced and Non-induced Forbidden Subposet Problems

- Mathematics, Computer Science
- Electron. J. Comb.
- 2015

The asymptotic behavior of La(n,P) is determined, the maximum size that an induced P-free subposet of the Boolean lattice B_n can have for the case when P is the complete two-level poset or the complete multi-level Poset K_{r,s,t} when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. Expand

Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2017

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… Expand

Set families with forbidden subposets

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2015

The Turan function of P, denoted $\pi^*(n,P)$, is the maximum size of a $P-free family of subsets of $\{1,\ldots,n\}$. Expand

Largest Family Without a Pair of Posets on Consecutive Levels of the Boolean Lattice

- Mathematics
- 2020

Suppose $k \ge 2$ is an integer. Let $Y_k$ be the poset with elements $x_1, x_2, y_1, y_2, \ldots, y_{k-1}$ such that $y_1 < y_2 < \cdots < y_{k-1} < x_1, x_2$ and let $Y_k'$ be the same poset but… Expand

Forbidden induced subposets in the grid

- Mathematics
- 2017

In this short paper, we prove the following generalization of a result of Methuku and Palvolgyi. Let $P$ be a poset, then there exists a constant $C_{P}$ with the following property. Let $k$ and $n$… Expand

#### References

SHOWING 1-10 OF 17 REFERENCES

A Note on the Largest Size of Families of Sets with a Forbidden Poset

- Mathematics, Computer Science
- Order
- 2014

An improved upper bound is provided on the size of families of subsets of [n] that do no contain a given poset P as a subposet that can be any positive integer less than $\lceil \frac{n}{2}\rceil$. Expand

On crown-free families of subsets

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2014

This paper proves that La ( n, O 2 t ) = ( 1 + o ( 1 ) ) ( n ⌊ n 2 ⌋ ) for all odd t ≥ 7 and that this is true for all even t ≥ 4. Expand

Poset-free families and Lubell-boundedness

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2015

Given a finite poset P, we consider the largest size La ( n , P ) of a family F of subsets of n ] : = { 1 , ? , n } that contains no subposet P. This continues the study of the asymptotic growth of… Expand

Diamond-free families

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2012

It is conjectured that @p(P):=lim"n"->"~La(n,P)/(n@?n2@?) exists for general posets P, and, moreover, it is an integer. Expand

No four subsets forming an N

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2008

Borders are given on how large F can be such that no four distinct sets A,B,C,D@?F satisfy A@?B, C@? B, C @?D, and the maximum size satisfies (n@?n2@?)(1+1n+@W(1n^2), which is very similar to the best-known bounds for the more restrictive problem of F avoiding three sets B,D,D. Expand

Induced and Non-induced Forbidden Subposet Problems

- Mathematics, Computer Science
- Electron. J. Comb.
- 2015

The asymptotic behavior of La(n,P) is determined, the maximum size that an induced P-free subposet of the Boolean lattice B_n can have for the case when P is the complete two-level poset or the complete multi-level Poset K_{r,s,t} when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. Expand

Largest Families Without an r-Fork

- Mathematics, Computer Science
- Order
- 2007

The maximum size of a finite set, F, is asymptotically determined up to the second term, improving the result of Tran. Expand

Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2017

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… Expand

The method of double chains for largest families with excluded subposets

- Mathematics, Computer Science
- Electron. J. Graph Theory Appl.
- 2013

A new method is introduced, counting the intersections of $\mathcal{F}$ with double chains, rather than chains, to prove the theorems of La(n,P) for infinitely many P posets. Expand

On a lemma of Littlewood and Offord

- Mathematics
- 1945

Remark. Choose Xi = l, n even. Then the interval ( — 1, + 1 ) contains Cn,m s u m s ^ i e ^ , which shows that our theorem is best possible. We clearly can assume that all the Xi are not less than 1.… Expand