Strong Splitter Theorem

The Splitter Theorem states that, if N is a 3-connected proper minor of a 3-connected matroid M such that, if N is a wheel or whirl then M has no larger wheel or whirl, respectively, then there is a sequence M ₀, . . . , M _n of 3-connected matroids with ${M_0 \cong N}$ , M _n = M and for ${i \in \{1, \ldots , n}\}$ , M _i is a single-element extension or coextension of M _i?1. Observe that there is no condition on how many extensions may occur before a coextension must occur. We give a strengthening of the Splitter Theorem, as a result of which we can obtain, up to isomorphism, M starting with N and at each step doing a 3-connected single-element extension or coextension, such that at most two consecutive single-element extensions occur in the sequence (unless the rank of thematroids involved is r(M)). Moreover, if two consecutive single-element extensions by elements {e, f} are followed by a coextension by element g, then {e, f , g} form a triad in the resulting matroid.     

A splitting theorem on smooth metric measure spaces

We consider a smooth metric measure space (M, g, e ^?f dv). Let ?? _f be its weighted Laplacian. Assuming that ??₁(?? _f ) is positive and the m-dimensional Bakry-émery curvature is bounded below in terms of ??₁(?? _f ), we prove a splitting theorem for (M, g, e ^?f dv). This theorem generalizes previous results by Lam and Li-Wang (Trans Am Math Soc 362:5043?C5062, 2010; J Diff Geom 58:501?C534, 2001; see also J Diff Geom 62:143?C162, 2002).     

On minor-minimally-connected matroids

By a well-known result of Tutte, if e is an element of a connected matroid M, then either the deletion or the contraction of e from M is connected. If, for every element of M, exactly one of these minors is connected, then we call M minor-minimally-connected. This paper characterizes such matroids and shows that they must contain a number of two-element circuits or cocircuits. In addition, a new bound is proved on the number of 2-cocircuits in a minimally connected matroid.     

A Liouville-Type Theorem for Smooth Metric Measure Spaces

For smooth metric measure spaces (M,g,e ^?f d _vol ) we prove a Liouville-type theorem when the Bakry–Emery Ricci tensor is nonnegative. This generalizes a result of Yau, which is recovered in the case f is constant. This result follows from a gradient estimate for f-harmonic functions on smooth metric measure spaces with Bakry–Emery Ricci tensor bounded from below.     

Almost-Graphic Matroids

A nongraphic matroid M is said to be almost-graphic if, for all elements e, either M\e or M/e is graphic. We determine completely the class of almost-graphic matroids, thereby answering a question posed by Oxley in his book “Matroid Theory.” A nonregular matroid is said to be almost-regular if, for all elements e, either M\e or M/e is regular. An element e for which both M\e and M/e are regular is called a regular element. We also determine the almost-regular matroids with at least one regular element.     

A formula on Heegaard genus of self-amalgamated 3-manifolds

Let M be an orientable compact irreducible and ∂-irreducible 3-manifold, and suppose ∂M consists of two boundary components F₁ and F₂ with g(F₁)=g(F₂)>1. Let Mf be the closed orientable 3-manifold obtained by identifying F₁ and F₂ via a homeomorphism f:F₁→F₂. With the assumption that M is small or g(M,F₁)=g(M)+g(F₁), we show that if f is sufficiently complicated, then g(Mf)=g(M,∂M)+1.     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.     

Galois groups of multivariate Tutte polynomials

The multivariate Tutte polynomial $\hat{Z}_{M}$ of a matroid M is a generalization of the standard two-variable version, obtained by assigning a separate variable v _e to each element e of the ground set E. It encodes the full structure of M. Let v={v _e } _e??E , let K be an arbitrary field, and suppose M is connected. We show that $\hat{Z}_{M}$ is irreducible over K(v), and give three self-contained proofs that the Galois group of $\hat{Z}_{M}$ over K(v) is the symmetric group of degree n, where n is the rank of M. An immediate consequence of this result is that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups. Finally, we conjecture a similar result for the standard Tutte polynomial of a connected matroid.     

Properties of matroids characterizable in terms of excluded matroids

Some properties π of matroids are characterizable in terms of a set S(π) of exluded matroids, that is, a matroid M satisfies property π if and only if M has no minor (series-minor, parallel-minor) isomorphic to a matroid in S(π). This note presents a necessary and sufficient condition for a property to be characterizable in terms of excluded 3-connected matroids.     

Extremal critically connected matroids

A connected matroid M is called a critically connected matroid if the deletion of any one element from M results in a disconnected matroid. We show that a critically connected matroid of rank n, n≥3, can have at most 2n?2 elements. We also show that a critically connected matroid of rank n on 2n?2 elements is isomorphic to the forest matroid of K₂, n?2.     

Smooth metric measure spaces with weighted Poincaré inequality

In this paper, we study smooth metric measure space (M, g, e ^?f dv) satisfying a weighted Poincaré inequality and establish a rigidity theorem for such a space under a suitable Bakry–Émery curvature lower bound. We also consider the space of f-harmonic functions with finite energy and prove a structure theorem.     

On fixing edges in graph minors

An area of much recent research activity has been involved with tying the presence of certain minors in a matroid to specific elements of this matroid. The aim of this paper is to show that there are exactly two 3-connected simple graphsG with at least four edges and the property that ifH is a 3-connected simple graph havingG as a minor ande andf are edges ofH, thenH has a minor isomorphic toG which containse andf in its edge set. Some extensions of this result are also considered.     

Degree bounded matroids and submodular flows

We consider two related problems, the Minimum Bounded Degree Matroid Basis problem and the Minimum Bounded Degree Submodular Flow problem. The first problem is a generalization of the Minimum Bounded Degree Spanning Tree problem: We are given a matroid and a hypergraph on its ground set with lower and upper bounds f(e)≤g(e) for each hyperedge e. The task is to find a minimum cost basis which contains at least f(e) and at most g(e) elements from each hyperedge e. In the second problem we have a submodular flow problem, a lower bound f(v) and an upper bound g(v) for each node v, and the task is to find a minimum cost 0–1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node v is between f(v) and g(v). Both of these problems are NP-hard (even the feasibility problems are NP-complete), but we show that they can be approximated in the following sense. Let opt be the value of the optimal solution. For the first problem we give an algorithm that finds a basis B of cost no more than opt such that f(e)?2Δ+1≤|B∩e|≤g(e)+2Δ?1 for every hyperedge e, where Δ is the maximum degree of the hypergraph. If there are only upper bounds (or only lower bounds), then the violation can be decreased to Δ?1. For the second problem we can find a 0–1 submodular flow of cost at most opt where the sum of the incoming and outgoing flow at each node v is between f(v)?1 and g(v)+1. These results can be applied to obtain approximation algorithms for several combinatorial optimization problems with degree constraints, including the Minimum Crossing Spanning Tree problem, the Minimum Bounded Degree Spanning Tree Union problem, the Minimum Bounded Degree Directed Cut Cover problem, and the Minimum Bounded Degree Graph Orientation problem.     

Equality of two-variable functional means generated by different measures

We consider two-variable functional means of the form $$M_{f,g;\mu}(x,y) := \left(\frac{f}{g}\right)^{-1}\left(\frac{\int\nolimits_{[0,1]} f(tx+(1-t)y)\,d\mu(t)}{\int\nolimits_{[0,1]}g(tx+(1-t)y)\,d\mu(t)}\right),$$ where f, g are continuous functions on a real interval such that g is positive, f/g is strictly monotonic and??? is a measure over the Borel sets of [0,1]. The main results concern the functional equation M _f,g;?? ?=?M _f,g;?? for the unknown functions f, g, where??? and ?? are given measures. Depending on the symmetry properties of the measures, various necessary conditions and sufficient conditions are established.     

On reformulated Zagreb indices

The first and second reformulated Zagreb indices are defined respectively in terms of edge-degrees as EM₁(G)=∑_e∈Edeg(e)² and EM₂(G)=∑_e∼fdeg(e)deg(f), where deg(e) denotes the degree of the edge e, and e∼f means that the edges e and f are adjacent. We give upper and lower bounds for the first reformulated Zagreb index, and lower bounds for the second reformulated Zagreb index. Then we determine the extremal n-vertex unicyclic graphs with minimum and maximum first and second Zagreb indices, respectively. Furthermore, we introduce another generalization of Zagreb indices.     

Minors of a random binary matroid

Let A be an n × m matrix over GF ₂ where each column consists of k ones, and let M be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant C_M such that m ≥ C_Mn² implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = A _n,m,k are chosen randomly, then there are constants k_M,L_M such that k ≥ k_M and m ≥ L_Mn implies that A contains M as a minor with high probability .     

A composition for matroids

The composition of a quotient matroid Q over a collection of component matroids f₁, …, f_n indexed on the cells of Q, is described. This composition, called quotient composition, may be viewed as an application of clutter composition to matroids, or as a generalization of matroid direct sum composition to the next higher connectivity. It may also be viewed as equivalent to compositions described by Minty in 1966, and Brylawski in 1971.Quotient composition is characterized, and the circuits and rank function of a composed matroid are given. Various other properties are described, along with a category for quotient composition.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.