BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given D and γ>0, whenever c>0 is sufficiently small and n sufficiently large, if G is a family of D-degenerate graphs of individual orders at most n, maximum degrees at most logncn, and total number of edges at most (1−γ)(2n), then G packs into the complete graph Kn. Our proof proceeds by analysing a natural random greedy packing algorithm. This version of the manuscript corrects a small error that appeared in the published version [Adv Math, 354 (2019), 106739].
We prove that there is c>0 such that for all sufficiently large n, if T1,…,Tn are any trees such that Ti has i vertices and maximum degree at most cn/logn, then {T1,…,Tn} packs into Kn. Our main result actually allows to replace the host graph Kn by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.
We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F=K_2 gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings, and discuss connections with property testing. As an application of our theory, we determine the asymptotically almost sure F-tiling number of inhomogeneous random graphs \mathbb{G}(n,W). As another application, in an accompanying paper [Hladky, Hu, Piguet: Komlos's tiling theorem via graphon covers, preprint] we give a proof of a strengthening of a theorem of Komlos [Komlos: Tiling Turán Theorems, Combinatorica, 2000].
We prove the following version of the Loebl-Komlos-Sos Conjecture: For every alpha>0 there exists a number M such that for every k>M every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: we decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. However, the decomposition given by the Regularity Lemma is not of help when G is sparse. To surmount this shortcoming we use a more general decomposition technique: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and two other objects each exhibiting certain expansion properties.
Let Knr denote the complete r-uniform hypergraph on n vertices. A matching M in a hypergraph is a set of pairwise vertex disjoint edges. Recent Ramsey-type results rely on lemmas about the size of monochromatic matchings. A starting point for this study comes from a well-known result of Alon, Frankl, and Lovász (1986). Our motivation is to find the smallest n such that every t-coloring of Knr contains an s-colored matching of size k. It has been conjectured that in every coloring of the edges of Knr with 3 colors there is a 2-colored matching of size at least k provided that n≥kr+⌊r+1k−1⌋. The smallest test case is when r=3 and k=4. We prove that in every 3-coloring of the edges of K123 there is a 2-colored matching of size 4.
Kelly, Kuehn and Osthus conjectured that for any l>3 and the smallest number k>2 that does not divide l, any large enough oriented graph G with minimum indegree and minimum outdegree at least \lfloor |V(G)|/k\rfloor +1 contains a directed cycle of length l. We prove this conjecture asymptotically for the case when l is large enough compared to k and k>6. The case when k<7 was already settled asymptotically by Kelly, Kuehn and Osthus.
Loebl, Komlos, and Sos conjectured that if at least half of the vertices of a graph G have degree at least some natural number 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)|, assumed that n=O(k). Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(T_k,T_m)\leq k+m+o(k+m),as k+m tends to infinity.
We show that the class of finite rooted binary plane trees is a Ramsey class (with respect to topological embeddings that map leaves to leaves). That is, for all such trees P,H and every natural number k there exists a tree T such that for every k-coloring of the (topological) copies of P in T there exists a (topological) copy H' of H in T such that all copies of P in H' have the same color. When the trees are represented by the so-called rooted triple relation, the result gives rise to a Ramsey class of relational structures with respect to induced substructures.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.