2013/10/01 by Andrzej Czygrinow, Czygrinow, Andrzej, Louis DeBiasio +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1310.0481
34 pages, 4 figures. This is the unabridged version of the paper, containing the full proof of Theorem 1.7. The case when |δ_U-δ_V| is small and s>2 involves a lengthy case analysis, spanning pages 20-32; this section is not included in the "journal version"
arxiv created 2013/10/01 · arxiv updated 2013/10/03
The problem of determining the optimal minimum degree condition for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of Ks,s was solved by Zhao. Later Hladký and Schacht, and Czygrinow and DeBiasio determined the optimal minimum degree condition for a balanced bipartite graph on 2m(s+t) vertices to contain m vertex disjoint copies of Ks,t for fixed positive integers s<t. For a balanced bipartite graph G[U,V], let δU be the minimum degree over all vertices in U and δV be the minimum degree over all vertices in V. We consider the problem of determining the optimal value of δU+δV which guarantees that G can be tiled with Ks,s. We show that the optimal value depends on D:=|δV-δU|. When D is small, we show that δU+δV≥ n+3s-5 is best possible. As D becomes larger, we show that δU+δV can be made smaller, but no smaller than n+2s-2s1/2. However, when D=n-C for some constant C, we show that there exist graphs with δU+δV≥ n+s^s1/3 which cannot be tiled with Ks,s.