Rohan Kapadia

activity

20132020

most citedThe Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

23 citations · 27 across the 8 of their papers we have counts for

collaborators

9 papers

math.CO2020

Densities of minor-closed graph classes are rational

Rohan Kapadia, Sergey Norin

For a graph class $F$ , let $e x_{F} (n)$ denote the maximum number of edges in a graph in $F$ on $n$ vertices. We show that for every proper minor-close…

math.CO2019★ 2 cited

Asymptotic Density of Graphs Excluding Disconnected Minors

Rohan Kapadia, Sergey Norin, Yingjie Qian

For a graph $H$ , let $c_{\infty} (H) = n \to \infty lim max \frac{∣ E ( G ) ∣}{n},$ where the maximum is taken over all graphs $G$ on $n$ vertices not containing $H$ as a minor. Thus…

math.CO2015

Computing girth and cogirth in perturbed graphic matroids

Jim Geelen, Rohan Kapadia

We give polynomial-time randomized algorithms for computing the girth and the cogirth of binary matroids that are low-rank perturbations of graphic matroids.

math.CO2015

The extremal functions of classes of matroids of bounded branch-width

Rohan Kapadia

For a set of matroids $M$ , let $e x_{M} (n)$ be the maximum size of a simple rank- $n$ matroid in $M$ . We prove that, for any finite field $F$ , if…

math.CO2014★ 1 cited

Lines, betweenness and metric spaces

Pierre Aboulker, Xiaomin Chen, Guangda Huzhang +2

A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured that this…

math.MG2013★ 23 cited

The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

Pierre Aboulker, Rohan Kapadia

A special case of a theorem of De Bruijn and Erdős asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured…

math.CO2013

Matroids with a modular 4-point line

Rohan Kapadia

A result of Seymour implies that any 3-connected matroid with a modular 3-point line is binary. We prove a similar characterization for 3-connected matroids with modular 4-point li…

math.CO2013★ 1 cited

Representation of matroids with a modular plane

Jim Geelen, Rohan Kapadia

We prove that if M is a vertically 4-connected matroid with a modular flat X of rank at least three, then every representation of M | X over a finite field F extends to a unique F-…

math.CO2013

Representability of matroids with a large projective geometry minor

Jim Geelen, Rohan Kapadia

We prove that for each prime power $q$ there is an integer $n$ such that if $M$ is a $3$ -connected, representable matroid with a PG $(n - 1, q)$ -minor and no $U_{2, q^{2} + 1}$ -minor, then…