Géza Tóth "Disjointness graphs of short polygonal chains"
Géza Tóth from Alfréd Rényi Institute of Mathematics will give the talk "Disjointness graphs of short polygonal chain" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.
Abstract:
The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is $\chi$-bounded, that is, its chromatic number $\chi(G)$ is upper bounded by a function of its clique number $\omega(G)$.
We show that this statement does not remain true for systems of polygonal chains of length $2$. Moreover, for polygonal chains of length $3$ the disjointness graph have arbitrarily large girth and chromatic number. We discuss some other, related results.
Joint work with János Pach and Gábor Tardos.
Watch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.