CEU Electronic Theses and Dissertations, 2022
| Author | Ghosh, Debarun |
|---|---|
| Title | Some problems in Extremal Combinatorics |
| Summary | My thesis looks into various problems in the field of Extremal Combinatorics. We work on the classical Tur\'an problem for graphs before branching out into ``Generalized Tur\'an problems". Specifically, we were interested in the growing field of Planar Tur\'an problems. We also explore the natural generalization of Tur\'an type problems in hypergraphs. In addition, we apply the concepts of Planar Extremal Graph Theory in determining the Wiener index of planar graphs. The thesis contains six chapters. The first chapter introduces the field of Extremal Graph Theory and Tur\'an type problems for graphs and hypergraphs. We delve into the basic notations and famous theorems, which laid the foundations of Extremal Graph Theory and its generalizations. The Tur\'an number of a graph $H$, denoted by $\ex(n, H)$, is the maximum number of edges in an $n$-vertex graph that does not have $H$ as a subgraph. Erd\H{o}s-Stone-Simonovits Theorem asserts that $\ex(n,H)=\left (1-\frac{1}{\ch i(H)-1}\right){ \binom{n}{2}}+o (n^2)$, where $\chi(H)$ is the chromatic number of $H$. If $H$ is non-bipartite, this result is an asymptotic form of $\ex(n,H)$, but if $H$ is bipartite, the order of magnitude of $\ex(n,H)$ is in general open. Even when the graph $H$ is non-bipartite, it is still interesting to know the order of magnitude of lower terms for $\ex(n,H)$. Let $TP_k$ be the triangular pyramid of $k$-layers. For $k\geq 1$, the chromatic number of $TP_k$ is $3$. In Chapter 2, we determine that $\ex(n,TP_3)= \frac{1}{4}n^2+n+o(n)$, and pose a conjecture for $\ex(n,TP_4)$. These results are based on the paper ``The Tur\'an Number of the Triangular Pyramid of $3$-Layers", co-authored by Gy\H{o}ri, Paulos, Xiao and Zamora. Now we look at problems in generalised Tur\'an numbers. Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Tur\'an number of $H$. It is denoted by ${\rm ex}_{\mathcal{P}}(n,H)$ and was initiated by Dowden (2016). Unfortunately, the case when the forbidden subgraph is a complete graph (i.e., the analog to Tur\'an) and stars is fairly trivial. The next most natural type of graph to investigate is perhaps a cycle. Dowden obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Lan, Shi and Song continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In Chapter 3, we improve this result and give the following sharp upper bound: ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$. These results are based on the paper ``Planar Tur\'an number of the $6$-cycle", co-authored by Gy\H{o}ri, Martin, Paulos and Xiao. Another generalization of the planar Tur\'an number of stars are the double stars as the forbidden graph. Double stars are two adjacent vertices of degree $m$ and $n$ respectively, and are denoted by $S_{m,n}$. It is easy to see that $\ex(n, S_{m,n}) = 3n-6$, for $m\geq2$ and $n\geq 6$. In Chapter 4, we determine the upper bounds for $\ex_{\p}(n,S_{2,2})$, $\ex_{\p}(n,S_{2,3})$, $\ex_{\p}(n,S_{2,4})$, $\ex_{\p}(n,S_{2,5})$, $\ex_{\p}(n,S_{3,3})$ and $\ex_{\p}(n,S_{3,4})$. Moreover, the bound for $\ex_{\p}(n,S_{2,2})$ is sharp. These results are based upon the ongoing paper ``Planar Tur\'an Number of Double Stars", co-authored by Gy\H{o}ri, Paulos and Xiao. Next, we consider a Tur\'an type problem in the field of Hypergraphs. One of the first problems in Extremal Graph Theory was the maximum number of edges that a triangle-free graph can have. Mantel solved this, which built the foundations of what we know as Extremal Graph Theory. The natural progression was to ask the maximum number of edges in a $k$-book free graph. A $k$-book, denoted by $B_k$, is $k$ triangles sharing a common edge. In the early 2000s, Gy\H{o}ri solved the hypergraph analog of the maximum number of hyperedges in a triangle-free hypergraph. In a hypergraph, $k$-book denotes $k$ Berge triangles sharing a common edge. Let $\text{ex}_3(n,\mathcal{F})$ denote the maximum number of hyperedges in a Berge-$\mathcal{F}$-free hypergraph on $n$ vertices. In Chapter 5, we prove $\text{ex}_3(n, B_k)=\dfrac{n^2 }{8}(1+o(1))$. These results are from the paper ``Book free $3$-Uniform Hypergraphs", co-authored by Gy\H{o}ri, Nagy-Gy\"{o}rgy, Paulos, Xiao, and Zamora. The Wiener index is the sum of the distances between all pairs of vertices in a connected graph. The Wiener index of an $n$-vertex maximal planar graph was conjectured to be at most $\lfloor\frac{1 }{18}(n^3+3n^2) \rfloor$. In the last chapter, we prove this conjecture and determine the unique $n$-vertex maximal planar graph attaining this maximum. These results are from the paper ``The maximum Wiener index of maximal planar graphs", co-authored by Gy\H{o}ri, Paulos, Salia, and Zamora. |
| Supervisor | Gyori, Ervin |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2022/ghosh_debarun.pdf |
Visit the CEU Library.
© 2007-2021, Central European University