Loading Events

« All Events

  • This event has passed.

Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

Tuesday, November 22, 2022 @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices.  A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge.

A simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all hypertrees $T$ of order at most $\frac{n+3}{2}$. On the other hand, it is not immediately clear whether one can always find larger hypertrees in $G$. In 2011, Goodall and de Mier proved that a Steiner triple system $G$ contains at least one spanning tree. However, one cannot expect the Steiner triple system to contain all possible spanning trees, as there are many Steiner triple systems that avoid numerous spanning trees as subgraphs. Hence it is natural to wonder how much one can improve the bound from the greedy algorithm.

Indeed, Elliott and Rödl conjectured that an $n$-vertex Steiner triple system $G$ contains all hypertrees of order at most $(1-o(1))n$. We prove the conjecture by Elliott and Rödl.

This is joint work with Jaehoon Kim, Joonkyung Lee, and Abhishek Methuku.


Tuesday, November 22, 2022
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.