 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, October 30, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Stoyan Dimitrov (University of Sofia)

## New bounds for the Vertex Folkman number $F(2_{7};5)$

Vertex Folkman number is defined as $F_{v}(a_{1}, a_{2},..,a_{r};q)= \min\{ |V(G)| : G\xrightarrow{v} (a_{1}, a_{2},..,a_{r})$ and $\omega (G) < q\}$. Here $G\xrightarrow{v} (a_{1}, a_{2},...,a_{r})$ means that in every $r$ - coloring of the vertices of G, for some color $i\in\{1,2, \ldots ,r\}$, there exists a monochromatic clique $K_{a_{i}}$. In the case of $a_{1} = a_{2} = \ldots = a_{r} = 2$, we write $F(2_{r};q)$. This case is of special importance, because $G\xrightarrow{v} (a_{1}, a_{2},...,a_{r})$ is equivalent to $\chi (G) > r$. Only one among the numbers $F(2_{r};q)$, $q\geq r-1$ and only three among the numbers $F(2_{r};r-2)$ are still not known. The focus of this work is on one of them, namely $F(2_{7};5)$.

It is previously known that $F(2_{7};5)>15$ (Nenov, 2009) and $F(2_{7};5)\leq 47$ (follows easily from a graph construction method by Mycielski, 1955). In this talk we explain how the new lower bound $F(2_{7};5)>17$ was obtained with the help of computer - assisted graph generation methods. Moreover, we present a simple proof of the upper bound $F(2_{7};5)\leq 22$.

Joint work with Nedyalko Nenov

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks