Student: | Michael Skotnica |
---|---|
Contact: | "surname"-at-kam.mff.cuni.cz |
School: | Faculty of Mathematics and Physics, Charles University, Czech Republic |
Problem(s): | High school partitions |
I am a member of the Czech group and I am working on a problem of High school partitions together with Josef Minarik. Our mentor is Shay Moran. For the descriptions of other problems of the Czech group, please see the following web pages:
We are given a directed graph (digraph) $G(V,E)$ such that the out-degree of each vertex is at least 3. A partition of $V$ into sets $P_1, P_2$ is called legal if
This corresponds to the following situation. Consider a set students, and assume each student $s$ writes down a list of 3 friends with whom $s$ wants to be in the same class. The legal partition then corresponds to the partition of students into two class such that each students has at least one friend in the same class.
In 1983, Thomassen [1] proved that each directed graph with all vertices of out-degree at least 3 contains two disjoint cycles. This immediately leads to the fact that such graph has at least one legal partition.
Our goals:
During the first week, we read articles about this problem, we learned known results and prepared the presentation.
We tried to find more than one legal partition in each digraph with all vertices of out-degree $\geq 3$. We found a way how to obtain at least two legal partitions.
Let $\Phi(d, s)$ denote the fact that in each digraph with all vertices of out-degree at least $d$ every $s$-tuple of vertices is separable. We explored relations between $\Phi(d,s)$ for several $d,s$.
We found another interesting relations between $\Phi(d,s)$ for several $d,s$.
We tried to find a graph with all vertices of out-degree at least $3$ and with unseparable pair of vertices using integer linear programming and CSP. However, without any success.
Our main goal this week was to prove that at least in each vertex-transitive digraphs with all vertices of out-degree $3$ every pair of vertices is separable. We obtained some partial results.