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.
어떤 그래프의 모임 $\mathcal{G}$가 강한 에르되시-하이날 성질을 가진다는 것은 상수 $c = c(\mathcal{G}) > 0$가 존재하여 $\mathcal{G}$의 각 원소 $G$마다 $G$ 또는 그 여 그래프 $\overline{G}$가 어떤 $m \geq \lfloor c |V(G)| \rfloor$에 대해 완전 이분 그래프 $K_{m, m}$을 부분그래프로 가짐을 의미한다. 본 연구는 모든 현 그래프의 모임은 상수 $c = \frac{2}{9}$에 대해 강한 에르되시-하이날 성질을 가짐을 증명한다. 강한 에르되시-하이날 성질을 함의하는 다색의 강한 에르되시-하이날 성질 이라고 불리는 속성이 기하학적인 대상에 대해 Alon 등과 Fox 등에 의해 논의되어진 바 있다. 같은 맥락에서, 현 그래프의 모임과 평면 위의 볼록 집합들의 교차 그래프의 모임은 각각 다색의 강한 에르되시-하이날 성질을 가지지 않음을 보인다. 이외에 연관이 있는 그래프들에 대한 에르되시-하이날 유형의 성질들을 논의한다.
다음 주제로, 각 다포체의 포를 전부 모은 하이퍼그래프의 횡단수에 대해 고찰한다. 모든 볼록 다포체는 그 꼭지점들의 절반만을 사용하여 그것의 모든 포를 만나게 할 수 있다고 추측된다. 본 논문에서는 3차원 스택 다포체의 포를 모은 2차원 스택 구체라는 하이퍼그래프의 횡단수에 대한 새로운 하계를 제시한다.
마지막으로, 협동적인 조건 하에 이분 그래프 내의 다색 매칭의 존재성에 관한 결과를 조합론적인 방법으로 증명한다. 최근 동일한 결과가 Holmsen과 Lee에 의해 위상수학적인 방법으로 증명되었는데, 해당 증명에 사용된 그래프 컴플렉스의 위상수학적 성질은 볼록 집합들의 신경들 또한 만족함이 알려져 있다. 이와 같은 관점에서 협동적인 조건을 가진 이산기하 분야의 정리들과 본 논문의 결과 사이의 관계를 재조명한다.
