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.