BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221122T163000
DTEND;TZID=Asia/Seoul:20221122T173000
DTSTAMP:20260419T224814
CREATED:20221018T043943Z
LAST-MODIFIED:20240707T074455Z
UID:6362-1669134600-1669138200@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
DESCRIPTION: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. \nA 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. \nIndeed\, 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. \nThis is joint work with Jaehoon Kim\, Joonkyung Lee\, and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2022-11-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR