DIMACS logo

Josef Cibulka

REU 2005

Welcome! I'm student of computer science at Charles University in Prague, Czech Republic. This september I'm finishing the third out of five years of the undergraduate study. I'm interested in combinatorics and graph theory.
I'm working on the REU project together with Jan Hladky and Marek Krcal. Leader of our group is Martin Balek. Our advisors are Eric Allender and Jeff Kahn.


Our project is to try to make some progress in solving several open problems.
You can find here some of the problems proposed by Jeff Kahn, the problems proposed by Eric Allender are on Marek's page.

Problem 1: Let G be an undirected graph. We call its subgraph a forest, if it doesn't contain any cycle. Let`s denote by n, n(e), n(ef) the number of all forests contained in G, those containing edge e and those containing both e and f, respectively. Conjecture which we are trying to prove or disprove says that n*n(ef)<=n(e)*n(f).

Problem 2: We denote by A,B the fact, that a forest contains a path between vertices s and t, resp. between u and v. In this case it seems that n(AB)*n()>=n(A)*n(B). It was proved that if the first conjecture is true, then this one is true, as well.

The edges of a graph can be viewed as vectors in space of dimension |V|. Edge is then a vector with 1 at places corresponding to the vertices that are joined by this edge and 0 at all the other places. Now we can generalize the previous conjectures to vector spaces:
Problem 2': Let X be a subset of vectorspace V. Let x,y be from V. If x can be written as a linear combination of vectors from X, we say that x lies in the span of X. Let n, n(x), n(xy) denote the number of all independent subsets of X, those containing x in their span and those containing both x and y in their span, respectively. Then n*n(xy)>=n(e)*n(f). This conjecture is believed not to be true, but noone has found an counterexample yet.
We can do the same generalization for the first conjecture, but there has already been found an counterexample.

Problem 3: Let T be a binary tree with some of its vertices colored with 4 colors called 1-4. We are also given the colors of its leaves. Now we randomly properly color (i.e.vertices sharing an edge must have different colors) all the remaining vertices. Now for each color i, we have probability p(i), that the root is colored by i. The question is whether those probabilities change if we change the colors of the leaves. This is obviously not true when the depth of the tree is small, but we want to show that the probabilities are becoming more and more similar when the depth grows to infinity.


Progress: 2005/07/22 The Problem 1 can be posed for spanning trees instead of spanning forests, but it has already been proven using theory of electrical networks and recently a combinatorial proof was found as well, see [1]. We have found a simpler proof, that uses techniques, that might be useful for spanning trees as well.

2005/07/07 We believed we had proven the path conjecture (Problem 2), you can download the proof in pdf or in postscript.
2005/07/10 Unfortunately, the proof doesn`t work - here is a counterexamle for the uniqueness of the transformation at the end of the proof.


References: [1] YoungBin Choe, A Combinatorial proof of Rayleigh formula for graphs, 2004