During 12. and 13. of Juny 2019 there was Dimea Days 2019 first run in the center of Brno, Czech Republic. The event took place at the museum at ‘Zelný trh’ near the main bus and train station ‘Hlavní nádraží’. The programme consisted mainly of eight cca 1h invited talks and one 1h10m poster session for presenting new research. The talks were combinatorial in nature and introduced the following concepts.
- pairwise crossing number - given N points in a plane what is the largest number of segments (starting and ending in disjoint given points) which mutually cross each other
- 1935 Erdős-Szekeres in each 2D point set there are log(n) points in convex position
- 1960 log(n) was shown to be 2log(n) up to additive constant; which guarantees the crossing number to be at least log(n)
- 1994, 1997 Valtr
- is this number linear in N? (open)
- Parch and Rubin got n/(2^{\sqrt(\log n)})
- embedding 2-complexes into 3d-space - we have ‘graphs’ in 3d (vertices, edges, and faces) the question if they can be embedded in 3d without corssing faces
- cycle-complete Ramsey numbers - when does 2-colored (red/blue) clique contain either red C_l or a K_n?
- cyclic connectivity - similarly to k-connectivity, what is the number of edges such that given any two cycles in a graph we can remove E edges to cut them into different components?
- sparse graphs - which graphs can be considered sparse? the bounded expansion and nowhere dense notions are introduced and some interesting alternative definitions of ND which help to argue an FPT algorithm for r-Dominating set
- fractional coloring - indtead of assigning only one color we choose a subset of B out of A colors such that adjacent vertices have disjoint sets of colors; A/B is the fraction coloring of the graph; can be described by LP, dual is connected to the weighted independent set
- Brook’s theorem – every graph can be colored by at most $\Delta$ colors, unless it is a clique or an odd cycle.
- interscetion graphs