My current web-page.

The following is my web-page from 199?.

I study in Prague (capital of Czech Republic), at the Faculty of Mathematics and Physics which is part of the Charles University. I am a participant of this year's REU program. I work together with Daniel Kral and Pavel Podbrdsky, our advisor is Endre Szemeredi (and partly Janos Komlos). We work on several problems in graph theory.

## Hamiltonian cycles

Let consider connected graphs with at least two vertices. For a graph G denote by h(G) the minimal numer k, such that G^k is Hamiltonian (we are taking the strong product of graphs to get the power). It was proved by Bermond, Germa and Heydemann that h(G) always exists and that G^k is Hamiltonian for any k >= h(G). Our goal is to prove, that h(G) <= D, where D is the maximal degree of vertex in G. We have already proved, that

• h(G) <= 13/12 . D + something small
• h(G) <= 3 if D = 3
• h(G) <= D for G being a star (D vertices connected to a central one)
• h(G) > c D, where c = ln 2 = 0.69...
• On July 5 we suceeded to prove the conjecture, we even got better bound then D. The proof will appear here soon.

## Shannon capacity

Shannon capacity is a interesting parameter of a graph, it is extremely difficult to compute. (It took several decades to compute it for pentagon, it is still unknown for cycle on seven vertices.) There is a conjecture due to Moishe Rosenfeld, that the Shannon capacity of a certain graph (complement of so-called Clebsch graph) is 16^(1/3). This would by very interesting, since this would be the very first example of a graph, for which the Shannon capacity is the third root of an integer.

## Ramsey type questions for bipartite graph

Suppose you have the edges of complete graph on N vertices by two colors. Classical Ramsey theorem says, you will alway find a complete subgraph on n vertices, which has all its edges colored by the same color, where n is approximately log N. There is also known a construction in which you cannot find any larger complete graph. Our question is almost the same, but instead of complete graph we are looking for a complete bipartite graph with n vertices in each partite. It is known, that we can always find graph with n approximately log N, there are construction showing that you cannot do any better, than square root of N. Our goal is to improve on of the bounds.

## Edge reconstruction

Let G, H be two graphs, let e_1, ..., e_m be edges of G, f_1, ..., f_m edges of H, and suppose that for any i graphs G \ e_i and H \ f_i are isomorphic. Are G and H isomorphic as well?
There are two trivial counterexamples for m = 2 or 3. So suppose, m >= 4. The Harary conjecture says, that then G and H are isomorphic. There is a theorem (due to Lovasz and Muller) that it is true for large m (m > n log n), but the general case is still open.