A constructive characterisation of circuits in the simple (2,1)‐sparse matroid

A simple graph is a (2, 1)‐circuit if and for every proper subgraph H of G. Motivated, in part, by ongoing work to understand unique realisations of graphs on surfaces, we derive a constructive characterisation of (2, 1)‐circuits. The characterisation uses the well‐known 1‐extension and X‐replacement operations as well as several summation moves to glue together (2, 1)‐circuits over small cutsets.     

A simple approach to some basic results in matroid theory

The bases and the cocircuits of a matroid form a blocking pair of clutters; this fact leads to simple proofs of some basic and well-known facts about matroids, including a variety of axiomatizations.     

On the (co)girth of a connected matroid

This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids.     

A simple proof that every matroid is an intersection of fundamental transversal matroids

We give a new proof of a theorem of Bondy and Welsh. Our proof is simpler than previous ones in that it makes no use of Hall's theorem on the existence of a transversal of a family of sets.     

A note on the weak (2,2)-Conjecture

Let $G=(V,E)$ be any graph without isolated edges. The well known 1–2–3 Conjecture asserts that the edges of $G$ can be weighted with $1,2,3$ so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if $G$ additionally has no isolated triangles, then it can be edge decomposed into two subgraphs $G_1,G_2$ which fulfil the 1–2–3 Conjecture with just weights 1,2, i.e. such that there exist weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ so that for every $uv\in E$, if $uv\in E\left(G_i\right)$ then $d_{{\omega }_i}\left(u\right)\ne d_{{\omega }_i}\left(v\right)$, where $d_{{\omega }_i}\left(v\right)$ denotes the sum of weights incident with $v\in V$ in $G_i$ for $i=1,2$. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if $\delta \left(G\right)\ge 3660$, then $G$ can be decomposed into graphs $G_1,G_2$ for which weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ exist so that for every $uv\in E$, $d_{{\omega }_1}\left(u\right)\ne d_{{\omega }_1}\left(v\right)$ or $d_{{\omega }_2}\left(u\right)\ne d_{{\omega }_2}\left(v\right)$. In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1.     

A simple constructive approach to quadratic BSDEs with or without delay

This paper provides a simple approach for the consideration of quadratic BSDEs with bounded terminal conditions. Using solely probabilistic arguments, we retrieve the existence and uniqueness result derived via PDE-based methods by Kobylanski (2000) [14]. This approach is related to the study of quadratic BSDEs presented by Tevzadze (2008) [19]. Our argumentation, as in Tevzadze (2008) [19], highly relies on the theory of BMO martingales which was used for the first time for BSDEs by Hu et al. (2005) [12]. However, we avoid in our method any fixed point argument and use Malliavin calculus to overcome the difficulty. Our new scheme of proof allows also to extend the class of quadratic BSDEs, for which there exists a unique solution: we incorporate delayed quadratic BSDEs, whose driver depends on the recent past of the Y$Y$ component of the solution. When the delay vanishes, we verify that the solution of a delayed quadratic BSDE converges to the solution of the corresponding classical non-delayed quadratic BSDE.     

A characterisation of PSp(4,K)

This paper gives a characterization of the group PS_p(4K) over some algebraically closed field K of characteristic not 2 inside the class of simple K ^*-groups of finite Morley rank not interpreting a bad field using the structure of centralizers of involutions.     

A note on the production of matroid minors

The circuits containing some fixed element of a connected matroid (such a collection is called a port) provide a matroid generalization of the “path collections” of graphs. In this note we show how to translate forbidden minor theorems in matroid theory into results about ports — and we find that many theorems are strengthened by such translation. Those collections of sets which are “path collections” of graphs may then be characterized.     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.     

A nonuniform matroid which violates the isotopy conjecture

The Isotopy Conjecture for Oriented Matroids states that the realization space over the real number field of an oriented matroid is path-connected. We provide a nonuniform counterexample of rank 3 on 42 points.     

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.     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

A matroid generalization of a result of Dirac

This paper generalizes a theorem of Dirac for graphs by proving that ifM is a 3-connected matroid, then, for all pairs {a,b} of distinct elements ofM and all cocircuitsC ^* ofM, there is a circuit that contains {a,b} and meetsC ^*. It is also shown that, although the converse of this result fails, the specified condition can be used to characterize 3-connected matroids.The author's research was partially supported by a grant from the National Security Agency.     

A sharp bound on the size of a connected matroid

This paper proves that a connected matroid in which a largest circuit and a largest cocircuit have and elements, respectively, has at most elements. It is also shown that if is an element of and and are the sizes of a largest circuit containing and a largest cocircuit containing , then . Both these bounds are sharp and the first is proved using the second. The second inequality is an interesting companion to Lehman's width-length inequality which asserts that the former inequality can be reversed for regular matroids when and are replaced by the sizes of a smallest circuit containing and a smallest cocircuit containing . Moreover, it follows from the second inequality that if and are distinct vertices in a -connected loopless graph , then cannot exceed the product of the length of a longest -path and the size of a largest minimal edge-cut separating from .