More on a problem of Zarankiewicz

Dutta, Chinmoy ; Radhakrishnan, Jaikumar (2012) More on a problem of Zarankiewicz Arxiv-eprints . pp. 1-14.

PDF - Author Version

Official URL:


We show tight necessary and sufficient conditions on the sizes of small bipartite graphs whose union is a larger bipartite graph that has no large bipartite independent set. Our main result is a common generalization of two classical results in graph theory: the theorem of Kovari, Sos and Turan on the minimum number of edges in a bipartite graph that has no large independent set, and the theorem of Hansel (also Katona and Szemeredi and Krichevskii) on the sum of the sizes of bipartite graphs that can be used to construct a graph (non-necessarily bipartite) that has no large independent set. Our results unify the underlying combinatorial principles developed in the proof of tight lower bounds for depth-two superconcentrators.

Item Type:Article
Source:Copyright of this article belongs to Arxiv Publications.
Keywords:Zarankiewicz Problem; Superconcentrators; Bipartite Graphs; Independent Sets; Probabilistic Method
ID Code:89490
Deposited On:27 Apr 2012 13:48
Last Modified:19 May 2016 04:01

Repository Staff Only: item control page