Characterizing Combinatorial Geometries by Numerical Invariants

We show that the projective geometry PG(r − 1,q ) for r & 3 is the only rank- r(combinatorial) geometry with (q^r − 1) / (q − 1) points in which all lines have at least q + 1 points. For r = 3, these numerical invariants do not distinguish between projective planes of the same order, but they do distinguish projective planes from other rank-3 geometries. We give similar characterizations of affine geometries. In the core of the paper, we investigate the extent to which partition lattices and, more generally, Dowling lattices are characterized by similar information about their flats of small rank. We apply our results to characterizations of affine geometries, partition lattices, and Dowling lattices by Tutte polynomials, and to matroid reconstruction. In particular, we show that any matroid with the same Tutte polynomial as a Dowling lattice is a Dowling lattice.     

Circuits Through Cocircuits In A Graph With Extensions To Matroids

We show that for any k-connected graph having cocircumference c*, there is a cycle which intersects every cocycle of size c*-k + 2 or greater. We use this to show that in a 2-connected graph, there is a family of at most c* cycles for which each edge of the graph belongs to at least two cycles in the family. This settles a question raised by Oxley. A certain result known for cycles and cocycles in graphs is extended to matroids. It is shown that for a k-connected regular matroid having circumference c ≥ 2k if C₁ and C₂ are disjoint circuits satisfying r(C₁)+r(C₂)=r(C₁∪C₂), then |C₁|+|C₂|≤2(c-k + 1).     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

Moduli of symplectic instanton vector bundles of higher rank on projective space ℙ<Superscript>3</Superscript>

Symplectic instanton vector bundles on the projective space ℙ³ constitute a natural generalization of mathematical instantons of rank-2. We study the moduli space I _n;r of rank-2r symplectic instanton vector bundles on ℙ³ with r ≥ 2 and second Chern class n ≥ r, n ≡ r (mod 2). We introduce the notion of tame symplectic instantons by excluding a kind of pathological monads and show that the locus I _n;r ^* of tame symplectic instantons is irreducible and has the expected dimension, equal to 4n(r + 1) −r(2r + 1).     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

Rainbow and monochromatic circuits and cocircuits in binary matroids

Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly $n?r$ colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.     

Counterexamples to conjectures on 4-connected matroids

Tutte characterized binary matroids to be those matroids without aU ₄ ² minor. Bixby strengthened Tutte’s result, proving that each element of a 2-connected non-binary matroid is in someU ₄ ² minor. Seymour proved that each pair of elements in a 3-connected non-binary matroid is in someU ₄ ² minor and conjectured that each triple of elements in a 4-connected non-binary matroid is in someU ₄ ² minor. A related conjecture of Robertson is that each triple of elements in a 4-connected non-graphic matroid is in some circuit. This paper provides counterexamples to these two conjectures.     

Oriented matroids and Ky Fan’s theorem

L. Lovász (Matroids and Sperner’s Lemma, Europ. J. Comb. 1 (1980), 65–66) has shown that Sperner’s combinatorial lemma admits a generalization involving a matroid defined on the set of vertices of the associated triangulation. We prove that Ky Fan’s theorem admits an oriented matroid generalization of similar nature. Classical Ky Fan’s theorem is obtained as a corollary if the underlying oriented matroid is chosen to be the alternating matroid C ^m,r .     

Negatively Correlated Random Variables and Mason’s Conjecture for Independent Sets in Matroids

Mason’s Conjecture asserts that for an m-element rank r matroid the sequence is logarithmically concave, in which I _k is the number of independent k-sets of . A related conjecture in probability theory implies these inequalities provided that the set of independent sets of satisfies a strong negative correlation property we call the Rayleigh condition. This condition is known to hold for the set of bases of a regular matroid. We show that if ω is a weight function on a set system that satisfies the Rayleigh condition then is a convex delta-matroid and ω is logarithmically submodular. Thus, the hypothesis of the probabilistic conjecture leads inevitably to matroid theory. We also show that two-sums of matroids preserve the Rayleigh condition in four distinct senses, and hence that the Potts model of an iterated two-sums of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included. Research supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

On Random Representable Matroids

Results are obtained on the likely connectivity properties and sizes of circuits in the column dependence matroid of a random r × n matrix over a finite field, for large r and n. In a sense made precise in the paper, it is shown to be highly probable that when n is less than r such a matroid is the free matroid on n points, while if n exceeds r it is a connected matroid of rank r. Moreover, the connectivity can be strengthened under additional hypotheses on the growth of n and r, using the notion of vertical connectivity; and the values of k for which circuits of size k exist can be determined in terms of n and r.     

The switching game on unions of oriented matroids

In 1986, Hamidoune and Las Vergnas [3] introduced an oriented matroid version of the so-called Shannon’s switching game. They conjectured that the classification of the directed switching game on oriented matroids is identical to the classification of the non-oriented version. In this note, we support this conjecture by showing its validity for an infinite class of oriented matroids obtained as unions of rank-1 and/or rank-2 uniform oriented matroids.     

(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4]. Received: December 16, 1996 / Revised: September 17, 1997     

The two-well problem in three dimensions

We study properties of generalized convex hulls of the set with . If K contains no rank-1 connection we show that the quasiconvex hull of K is trivial if H belongs to a certain (large) neighbourhood of the identity. We also show that the polyconvex hull of K can be nontrivial if H is sufficiently far from the identity, while the (functional) rank-1 convex hull is always trivial. If the second well is replaced by a point then the polyconvex hull is trivial provided that there are no rank-1 connections. Received: March 25, 1999 / Accepted: April 23, 1999     

On a Sharp Degree Sum Condition for Disjoint Chorded Cycles in Graphs

Let r and s be nonnegative integers, and let G be a graph of order at least 3r + 4s. In Bialostocki et al. (Discrete Math 308:5886–5890, 2008), conjectured that if the minimum degree of G is at least 2r + 3s, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles, and they showed that the conjecture is true for r = 0, s = 2 and for s = 1. In this paper, we settle this conjecture completely by proving the following stronger statement; if the minimum degree sum of two nonadjacent vertices is at least 4r + 6s−1, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles.     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

A minor-based characterization of matroid 3-connectivity

It is well known that a matroid is 2-connected if and only if every 2-element set is contained in a circuit, or equivalently, a _U1,2$U_{1,2}$-minor. This paper proves that a matroid is 3-connected if and only if every 4-element set is contained in a minor isomorphic to a wheel of rank 3 or 4; a whirl of rank 2, 3, or 4; or the relaxation of a rank-3 whirl. Some variants of this result are also discussed.