General Information

Student: Josef Minařík
School: Faculty of Mathematics and Physics, Charles University
E-mail: minarjos00 (at) gmail (dot) com
Project: High school partitions

Project Description

Consider a group of students which is supposed to be separated into two classes. Every student has at least three friends among other students. Thomassen proved it is always possible to assign students into classes such that every student has at least one friend in the same class. Suppose we want to separate a certain pair of students, is it always possible?

Weekly Log

Week 1:
I read some papers about similar problems.
Week 2:
We tried to prove that there is more than one legal partition.
Week 3:
We considered separability of more than two vertices for higher degrees.
Week 4:
Discovering some relations between separability of vertices and minimal outdegree.
Week 5:
Coding some programs, trying to find some counter-examples (unsuccesfully).
Week 6:
Considering infinite graphs and strongly connected graphs.
Week 7:
We tried to prove that every vertex is separable in vertex transitive graphs.
Week 8:
Some partial results for transitive graphs.
Week 9:
Some more results for transitive graphs, using some probabalistic methods for regular graphs.