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
For a set of matroids M, let exM(n) be the maximum size of a simple rank-n matroid in M. We prove that, for any finite field F, if M is a minor-closed class of F-representable matroids of bounded branch-width, then limn→∞exM(n)/n exists and is a rational number, Δ. We also show that exM(n)−Δn is periodic when n is sufficiently large and that exM is achieved by a subclass of M of bounded path-width.
We give polynomial-time randomized algorithms for computing the girth and the cogirth of binary matroids that are low-rank perturbations of graphic matroids.
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 U2,q2+1-minor, then M is representable over GF(q). We also show that for ℓ>=2, if M is a 3-connected, representable matroid of sufficiently high rank with no U2,ℓ+2-minor and ∣E(M)∣≥(4ℓ)r(M)/2, then M is representable over a field of order at most ℓ.
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 holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with n points, either there is a line containing all the points or there are at least Ω(n) lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of Ω(n2/5) lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are Ω(n4/7) lines, improving the previous Ω(n2/7) bound. We also prove that the number of lines in an n-point metric space is at least n/5w, where w is the number of different distances in the space, and we give an Ω(n4/3) lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from \{1, 2, 3\}.
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 lines. We show that such a matroid is either representable over GF(3) or GF(4) or has an F7-minor and either an (F7−)- or (F7−)∗-minor.
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 a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs -- a graph G is called distance-hereditary if the distance between two vertices u and v in any connected induced subgraph H of G is equal to the distance between u and v in G.
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-representation of M. A corollary is that when F has order q, any vertically 4-connected matroid with a PG(2, F)-restriction is either F-representable or has a U_{2, q^2+1}-minor. We also show that no excluded minor for the class of F-representable matroids has a PG(2, F)-restriction.
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.