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
Suppose that k is a non-negative integer and a bipartite multigraph G is the union of N=⌊k+1k+2n⌋−(k+1) matchings M1,…,MN, each of size n. We show that G has a rainbow matching of size n−k, i.e. a matching of size n−k with all edges coming from different Mi's. Several choices of parameters relate to known results and conjectures.
We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.
In this paper we introduce a new clustering technique called Regularity Clustering. This new technique is based on the practical variants of the two constructive versions of the Regularity Lemma, a very useful tool in graph theory. The lemma claims that every graph can be partitioned into pseudo-random graphs. While the Regularity Lemma has become very important in proving theoretical results, it has no direct practical applications so far. An important reason for this lack of practical applications is that the graph under consideration has to be astronomically large. This requirement makes its application restrictive in practice where graphs typically are much smaller. In this paper we propose modifications of the constructive versions of the Regularity Lemma that work for smaller graphs as well. We call this the Practical Regularity partitioning algorithm. The partition obtained by this is used to build the reduced graph which can be viewed as a compressed representation of the original graph. Then we apply a pairwise clustering method such as spectral clustering on this reduced graph to get a clustering of the original graph that we call Regularity Clustering. We present results of using Regularity Clustering on a number of benchmark datasets and compare them with standard clustering techniques, such as k-means and spectral clustering. These empirical results are very encouraging. Thus in this paper we report an attempt to harness the power of the Regularity Lemma for real-world applications.
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.