Dhruv Mubayi

collaborators

7 papers

math.CO2009★ 6 cited

Almost all cancellative triple systems are tripartite

Jozsef Balogh, Dhruv Mubayi

A triple system is cancellative if no three of its distinct edges satisfy $A \cup B = A \cup C$ . It is tripartite if it has a vertex partition into three parts such that every edge h…

math.CO2009★ 3 cited

Counting substructures III: quadruple systems

Dhruv Mubayi

For various quadruple systems F, we give asymptotically sharp lower bounds on the number of copies of F in a quadruple system with a prescribed number of vertices and edges. Our re…

math.CO2009★ 1 cited

Counting substructures I: color critical graphs

Dhruv Mubayi

Let $F$ be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of $F$ in a graph with a prescribed number of v…

math.CO2009

Finding bipartite subgraphs efficiently

D. Mubayi, G. Turan

Polynomial algorithms are given for the following two problems: given a graph with $n$ vertices and $m$ edges, where $m \geq 3 n^{3/2}$ , find a complete balanced bipartite subgraph…

math.CO2009★ 2 cited

Counting substructures II: triple systems

Dhruv Mubayi

For various triple systems $F$ , we give tight lower bounds on the number of copies of $F$ in a triple system with a prescribed number of vertices and edges. These are the first suc…

math.CO2009★ 3 cited

Biclique Coverings and the Chromatic Number

Dhruv Mubayi, Sundar Vishwanathan

Consider a graph $G$ with chromatic number $k$ and a collection of complete bipartite graphs, or bicliques, that cover the edges of $G$ . We prove the following two results: \medski…