CEU Electronic Theses and Dissertations, 2015
| Author | Methuku, Abhishek |
|---|---|
| Title | On the size of the largest P-free families |
| Summary | 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 generalization of the well-known Sperner's theorem. In 1945, Erdos obtained the exact value of La(n, P) when P is a path poset, generalizing Sperner's theorem. A more formal study of this problem was initiated by Katona and Tarjan in 1983. Since then there have been numerous papers in this area and many open questions. One of the open questions was to obtain a good general bound on La(n, P) for an arbitrary poset P. Open questions concerning the exact (or at least asymptotic) value of La(n, P) for some specific posets P are also of great interest. In this thesis, we answer some of these open questions. We obtain a general bound on La(n, P) which is best possible upto a constant factor, improving the previous bounds due to Burcsi and Nagy and later Chen and Li. We also obtain the exact value of La(n, P) for an infinite class of posets and introduce a new method for doing so. |
| Supervisor | Katona, Gyula O.H. |
| Department | Mathematics MSc |
| Full text | https://www.etd.ceu.edu/2015/methuku_abhishek.pdf |
Visit the CEU Library.
© 2007-2021, Central European University