Loebl-Komlós-Sós conjecture: dense case
(with Jan Hladký): arXiv:0805.4834.
We prove a version of the Loebl-Komlós-Sós Conjecture for dense graphs. For any q>0 there exists a natural number n_0 such that for any n >n_0 and k>qn the following holds: if G be a graph of order n with at least n/2 vertices of degree at least k, then any tree of order k+1 is a subgraph of G.
Extended abstract published in Electronic Notes in Discrete Mathematics under the same name (see "published")
An approximate version of the Loebl-Komlós-Sós conjecture
(with Maya Stein): arXiv:0708.3355.
Loebl, Komlós, and Sós conjecture that if at least half of the vertices of a graph G have degree at least some k, then every tree with at most k edges is a subgraph of G. Our main result is an approximate version of this conjecture for large enough n=|V(G)|, and k linear in n. We extend our result to a slightly larger class of subgraphs. Namely, we show that G contains as subgraphs all bipartite connected graphs of order k+1 with at most k+c edges, where c is some constant in n. Also, we derive from our result an asymptotic bound for the Ramsey number of trees. We prove that r(T_k,T_m)\leq k+m+o(k+m), provided that liminf (k/m), liminf (m/k) >0.
Extended abstract published in Electronic Notes in Discrete Mathematics under the same name (see "published")
The Loebl Conjecture for trees of small diameter
(with Maya Stein): KAM Series (2005-730)
The Loebl conjecture asks whether any graph on n vertices, at least of of which have degree n/2, contains any tree of order n+1 as a subgraph. We prove the conjecture for trees with diameter at most 5.
not submitted: result generalized in The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars (see "published").
A canonical Ramsey-type theorem for finite subsets of N:
Comment.Math.Univ.Carolinae 44,2 (2003) 235-243.
T. Brown proved that whenever we color Pf (N) (the set of finite subsets of
natural numbers) with finitely many colors, we find a monochromatic structure, called
an arithmetic copy of an omega-forest.
In this paper we show a canonical extension of this theorem; i.e. whenever we color
Pf (N) with arbitrarily many colors, we find a canonically colored arithmetic copy of an
omega-forest. The five types of the canonical coloring are determined. This solves a problem
of T. Brown.
Loebl-Komlós-Sós Conjecture: dense case
(with Jan Hladký and Oliver Cooley): Electronic Notes in Discrete Mathematics, Vol 34 (2009), 597-601 . (extended abstract)
We prove a version of the Loebl-Komlós-Sós Conjecture for large dense graphs. For any q>0 there exists a natural number n' such that for any n>n' holds: If G has median degree at least k, then any tree of order at most k+1 is a subgraph of G.
An approximate version of the Loebl-Komlós-Sós conjecture
(with Maya Stein): Electronic Notes in Discrete Mathematics, Vol 29 (2007), 249-253. (extended abstract)
The Loebl-Komlós-Sós conjecture states that, given a graph G and a natural number k, if at least half the vertices of G have degree at least k, then any tree with at most k edges is a subgraph of G.
We prove an approximate version of this conjecture for large graphs and k linear in |V(G)|.
Diploma thesis: Teorie Rozkladù- Partition theory: pdf.