DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Holmsen, Andreas | - |
dc.contributor.advisor | 안드레아스 홈슨 | - |
dc.contributor.author | Cho, Minho | - |
dc.date.accessioned | 2023-06-22T19:33:49Z | - |
dc.date.available | 2023-06-22T19:33:49Z | - |
dc.date.issued | 2023 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=1030463&flag=dissertation | en_US |
dc.identifier.uri | http://hdl.handle.net/10203/308562 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 수리과학과, 2023.2,[vi, 73 p. :] | - |
dc.description.abstract | A graph class $\mathcal{G}$ has the strong Erd\H{o}s-Hajnal(EH) property if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m, m}$ as a subgraph where $m \geq \lfloor c |V(G)| \rfloor$. We prove that the class of chordal graphs satisfy the strong Erd\H{o}s-Hajnal property with constant $c = \frac{2}{9}$. A strengthening of the strong EH property which we call the colorful strong EH property was discussed in geometric settings by Alon et al. and by Fox et al. Inspired by their results, we disprove the colorful strong EH property of chordal graphs and intersection graphs of convex sets on the plane. Erd\H{o}s-Hajnal type properties for other related graph classes are also discussed. In the next topic, we consider the transversal number of facet hypergraphs of a certain family of polytopes. It is conjectured that every facet hypergraph of a convex polytope can be pierced by at most half of its vertices. We provide a new lower bound for the transversal number of stacked 2-spheres which are exactly facet hypergraphs of stacked 3-polytopes. Finally, we show the existence of rainbow matchings in bipartite graphs under a cooperative condition on color classes. Our proof is purely combinatorial. Holmsen and Lee obtained the same result using topological properties of certain graph complexes which is also enjoyed by the nerve of convex sets. Using those properties, we draw relations between our result and cooperative theorems in discrete geometry. | - |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Intersection graph▼aErdos-Hajnal property▼aStacked sphere▼aTransversal number▼aRainbow matching | - |
dc.subject | 교차그래프▼a에르되시-하이날 성질▼a스택 구체▼a횡단수▼a다색 매칭 | - |
dc.title | Extremal results on hypergraphs arising from geometric objects | - |
dc.title.alternative | 기하학적인 대상으로부터 발생하는 하이퍼그래프의 극단조합론적 결과 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 325007 | - |
dc.description.department | 한국과학기술원 :수리과학과, | - |
dc.contributor.alternativeauthor | 조민호 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.