DIMACS
DIMACS REU 2019

General Information

me
Student: Jan Soukup
Office: 450
School: Charles university
E-mail: soukja2@seznam.cz
Project: A forcing game on graphs

Project Description

  1. For a given integers m and k ≥ 2, and a fixed graph H we analyze following game played on a graph G by 2 players, plazer A and player B.

    It starts with a graph G with m vertices and no edges. Then players A and B take turns, as follows:

    • Player A either selects an independent set S of size k in G or decides to stop the game.
    • Player B modifies G by adding edges with both ends in S; he must add at least one edge, but may add more.
    At the end of the game, Player A wins if G contains H as an induced subgraph; and Player B wins otherwise.

    Variants where Player A does not see the graph G.

    • LOSE: Player A loses when he selects non-independent set.
    • SKIP: Turn is skipped when player A selects non-independent set.

  2. If G is a graph with no dominating edge, and for all v ∈ V(G), G∖v has a dominating edge, then G contains an induced C5.

Weekly Log

Week 1:
I read paper about problem problem 1) and I have given it some initial thoughts. Found some observation about problem 2)
Week 2:
During Monday we met with our mentor and discussed details about the problems. And we also presented our projects. Then we presented our plans to others.

We made some progress at the LOSE variant of the game (i.e. player A does not see the big graph and lose when he select a non-independent set.), by showing that player A can always force K3 or C4.

I also write a program solving some base cases of the original game but so far it can handle games of up to 9 vertices.

Week 3:
From now on I focuse solely on problem 2) (i.e. the game). We showed that we can force either Kc or Kc,c for arbitrary c in the LOSE variant of the game. We also showed that we can force paths.

But we mainly focused on the original variant of the game. And mostly on bounds for forcing paths and graphs that are easily forcible from paths. We showed some lower and upper bounds for number of vertices needed to force a path.

There was also an intresting talk about Strong perfect graph theorem and related problems.

Week 4 :

We had an excursion into the Bell labs on Monday. The talks there were very interesting.

During the week I mainly focused on improving the bounds for vertices needed to force an induced path in the original variant of the game. At first we were convinced that we need exponentially many of them but it turned out that the proof was not correct. At least we were able to modify it to a bound for vertices needed to force a component with high diameter. After that we found a construction that suggests we need just polynomially many of vertices to force an induced path.

Week 5 :

We firstly verified correctness of the construction for paths. And then we applied similar but more complicated construction that works for trees. And so, we need only polynomially many vertices to force an arbitrary tree.

Later in the week we met with our mentor, Sophie Spirkl, and we simplified and improved our proof. We also managed to use this tree construction to construct cycles of lenght at least 5. We still don't know if it also true for C4.

Week 6

We solved the C4case using Erdős-Hajnal conjecture. Andrej then decided to write down our results, whereas I tried to find out other new things. I was trying to use the conjecture to force even other classes of graphs but I was not able to use it. At least I read several papers about it and understand some current approaches aiming to solve the conjecture in its entirety. Then I focused on combined our approaches to show that we can force some other classes of graphs in polynomial time. In particular I focused on bipartite graphs.

Week 7

Early in the week we had another meeting with Sophie during which we showed that we can force several classes of bipartite graphs in polynomial time.

On Thursday we had our final presentation, and even though some Slovakian anomaly modified our presentation, I believe we succeeded in conveying our results.

Presentations

Additional Information