Seminár z teórie grafov - Christian Rubio-Montiel (13.10.2016)

vo štvrtok 13.10.2016 o 9:50 hod. v miestnosti M/213

10. 10. 2016 09.18 hod.
Od: Martin Škoviera

Prednášajúci: Christian Rubio-Montiel (Univerzita Komenskeho, Bratislava)

Názov: On crossing families

Termín: 13.10.2016, 9:50 hod., M/213

Abstrakt:
A geometric graph is a graph drawn in the plane such that its n vertices are points in general position, and its edges are straight-line segments.
Two edge-disjoint geometric subgraphs *cross* if there is an edge in the first subgraph and an edge in the second subgraph that have an interior point in common. A set of edge-disjoint geometric subgraphs is called *mutually crossing* if any two of their elements cross. We show that for any geometric complete graph there always exists a set of mutually crossing 2-paths (paths of length 2) of size at least \sqrt{n/2}, and a set of mutually crossing claw graphs (a star of tree leaves) of size at least n/6.

This is a joint work with Dolores Lara (Departamento de Computación, CINVESTAV, Mexico).