CEU Electronic Theses and Dissertations, 2008
| Author | Lemons, Nathan Wishard |
|---|---|
| Title | Tur'an Problems for Hypergraphs |
| Summary | We consider two different Tur'an-type problems for hypergraphs. The first concerns uniform and non-uniform hypergraphs avoiding cycles of a given length. Here we use the loosest definition of a cycle (due to Berge). We are able to bound the number of edges of l-uniform hypergraphs containing no cycle of length 2k+1 by O(n(k+1)/k) if l>2 and n is the number of vertices of the hypergraph. We give the same bound to l-uniform hypergraphs avoiding a cycle of length 2k. These orders of magnitudes are shown to be sharp when k = 2, 3 or 5. We also consider the problem for non-uniform hypergraphs. Here we are able to bound the total size of the hypergraph (the sum of the sizes of the edges) by O(n1+1/k) for hypergraphs H if either H contains no cycle of length 2k or H contains no cycle of length 2k + 1. The second problem is a perturbation of the famous Erd˝os-Ko-Rado Theorem. We find the largest possible unbalance of k-uniform hypergraphs whose edges have pairwise non-trivial intersections. The unbalance of such a hypergraph is defined as the size (number of edges) of the hypergraph minus the size of the largest degree in the hypergraph. |
| Supervisor | Gy"ori, Ervin |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2008/tphlen01.pdf |
Visit the CEU Library.
© 2007-2021, Central European University