컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0212 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | (DM) Discrete Mathematics (DM) |
| 발표시간(Time) | 20th-C-10:00 -- 10:20 |
| 영문제목 (Title(Eng.)) |
Constructions of geometric hypergraphs with high chromatic number and transversal ratio - an illustrative guide |
| 저자(Author(s)) |
Seunghun Lee1 KAIST1 |
| 초록본문(Abstract) | Given a hypergraph $H=(V,E)$, we say that $H$ is \textit{(weakly) $m$-colorable} if there is a coloring $c:V\to [m]$ such that every hyperedge of $H$ is not monochromatic. The \textit{(weak) chromatic number} of $H$, denoted by $\chi(H)$, is the smallest $m$ such that $H$ is $m$-colorable. A vertex subset $T \subseteq V$ is called a \textit{transversal} of $H$ if for every hyperedge $e$ of $H$ we have $T\cap e \ne \emptyset$. The \textit{transversal number} of $H$, denoted by $\tau(H)$, is the smallest size of a transversal in $H$. The \textit{transversal ratio} of $H$ is the quantity $\tau(H)/|V|$ which is between 0 and 1. Since a lower bound on the transversal ratio of $H$ gives a lower bound on $\chi(H)$, these two quantities are closely related to each other. We present constructions of geometric hypergraphs with high chromatic number and(or) transveral ratio. The ultimate conjecture on this line asks for a construction of $d$-polytopes for every $d\geq 4$ such that the supremum among the transversal ratios of the facet hypergraphs of those $d$-polytopes is eqaul to 1. As intermediate steps towards the conjecture, we will briefly consider constructions, by illustrations, regarding transversals and colorings coming from various types of simplicial complexes - neighborly spheres, simplicial complexes which are piecewise-linearly (or geometrically) embeddable in $\mathbb{R}^d$ and so on. This presentation is based on the two joint work; one with Joseph Briggs and Michael Gene Dobbins, and the other with Eran Nevo. |
| 분류기호 (MSC number(s)) |
05E45 |
| 키워드(Keyword(s)) | Coloring, chromatic number, transversal, hypergraph, simplicial complex, simplicial sphere, PL-embedding, geometric embedding |
| 강연 형태 (Language of Session (Talk)) |
English |