Matchings meeting quotas and their impact in the blow-up lemma

Citation
V. Rodl et al., Matchings meeting quotas and their impact in the blow-up lemma, SIAM J COMP, 31(2), 2001, pp. 428-446
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
428 - 446
Database
ISI
SICI code
0097-5397(20011011)31:2<428:MMQATI>2.0.ZU;2-C
Abstract
A bipartite graph G = (U,V;E) is called epsilon -regular if the edge densit y of every sufficiently large induced subgraph differs from the edge densit y of G by no more than. If, in addition, the degree of each vertex in G is between (d-epsilon) n and (d+epsilon) n, where d is the edge density of G a nd |U| = |V| = n, then G is called super (d,epsilon)-regular. In [Combinato rica, 19(1999), pp. 437-452] it was shown that if S subset ofU and T subset ofV are subsets of vertices in a super-regular bipartite graph G = ( U, V; E), and if a perfect matching M of G is chosen randomly, then the number o f edges of M that go between the sets S and T is roughly |S||T|/n. In this paper, we derandomize this result using the Erdos-Selfridge method of condi tional probabilities. As an application, we give an alternative constructiv e proof of the blow-up lemma of Komlos, Sarkozy, and Szemeredi (see [ Combi natorica, 17 (1997), pp. 109-123] and [Random Structures Algorithms, 12 (19 98), pp. 297-312]).