DIMACS REU 2020

General Information

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:

Project Description

High school partitions

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

  • $P_1, P_2 \neq \emptyset$,
  • $P_1 \cap P_2 = \emptyset$,
  • $P_1 \cup P_2 = V$,
  • the digraph induced by $P_1$ has all vertices of out-degree at least 1 as well as the digraph induced by $P_1$.

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:

  • Let $t(d, n)$ denote the minimum number of non-trivial legal partitions of a digraph with $n$ vertices and minimum out-degree $\geq d$. Provide upper and lower bounds on $t(d, n)$. By the result of Thomassen [1] we know $t(3, n) \geq 1$.
  • Prove or disprove: let $G = (V, E)$ be a digraph such that each vertex has out-degree $\geq 3$. Then, for every distinct $u, v \in V$ there exists a friendly partition of $V$ which separates $u, v$.

Weekly Log

Week 1:

During the first week, we read articles about this problem, we learned known results and prepared the presentation.

Week 2:

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.

Week 3:

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$.

Week 4:

We found another interesting relations between $\Phi(d,s)$ for several $d,s$.

Week 5:

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.

Week 6:

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.

References

Presentations

Additional Information