BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
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:20220907T163000
DTEND;TZID=Asia/Seoul:20220907T173000
DTSTAMP:20260419T020744
CREATED:20220614T112030Z
LAST-MODIFIED:20240705T171148Z
UID:5853-1662568200-1662571800@dimag.ibs.re.kr
SUMMARY:Dömötör Pálvölgyi\, C-P3O: Orientation of convex sets and other good covers
DESCRIPTION:We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular\, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems\, P3O (partial 3-order)\, are a natural generalization of posets\, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets\, p-P3O\, and P3O that emerge from convex sets\, C-P3O\, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O’s.\nBased on joint work with Agoston\, Damasdi\, and Keszegh:\nhttps://arxiv.org/abs/2206.01721\nhttps://arxiv.org/abs/2206.01723
URL:https://dimag.ibs.re.kr/event/2022-09-07/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220921T163000
DTEND;TZID=Asia/Seoul:20220921T173000
DTSTAMP:20260419T020744
CREATED:20220818T013812Z
LAST-MODIFIED:20240707T074721Z
UID:6050-1663777800-1663781400@dimag.ibs.re.kr
SUMMARY:Mehtaab Sawhney\, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
DESCRIPTION:An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e.\, if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs\, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay\, for which Erdős offered one of his notorious monetary prizes and the proof involves a wide range of different tools from Fourier analysis\, random matrix theory\, the theory of Boolean functions\, probabilistic combinatorics\, and low-rank approximation. \nJoint w. Matthew Kwan\, Ashwin Sah\, and Lisa Sauermann
URL:https://dimag.ibs.re.kr/event/2022-09-21/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220929T100000
DTEND;TZID=Asia/Seoul:20220929T110000
DTSTAMP:20260419T020744
CREATED:20220904T134540Z
LAST-MODIFIED:20240707T074627Z
UID:6134-1664445600-1664449200@dimag.ibs.re.kr
SUMMARY:Santiago Guzmán-Pro\, Local expressions of graphs classes
DESCRIPTION:A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes\, the set of minimal obstructions might be infinite\, or too complicated to describe. For instance\, for any $k\ge 3$\, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless\, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$ is $k$-colourable if and only if it admits an orientation with no directed walk on $k+1$ vertices. We say that a class of graphs $\mathcal{P}$ is expressible by forbidden orientations if there is a finite set $F$ of oriented graphs such that $\mathcal{P}$ is the class of graphs that admit an $F$-free orientation. We are interested in understanding which graph classes are expressible by forbidden orientations (and why). In this talk\, we present some limitations of this expression system. In particular\, we show that the class of even-hole free graphs is not expressible by forbidden orientations. \nThroughout the talk\, we also mention some other related expression systems. In particular\, each of these systems provides a certification method to the $\mathcal{P}$-decision problem; i.e.\, decide if an input graph belongs to the class $\mathcal{P}$. We conclude this talk by proposing a general framework to talk about these expression systems. This framework allows us to formalize the question\, what can be certified this way? \nBased on a joint work with César Hernández-Cruz.
URL:https://dimag.ibs.re.kr/event/2022-09-29/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR