On minor-minimally 3-connected binary matroids

A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each e∈E(M), either M?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.     

Removing circuits in 3-connected binary matroids

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.     

Towards a splitter theorem for internally 4-connected binary matroids III

This paper proves a preliminary step towards a splitter theorem for internally 4-connected binary matroids. In particular, we show that, provided M   or M^?$M^{?}$ is not a cubic Möbius or planar ladder or a certain coextension thereof, an internally 4-connected binary matroid M with an internally 4-connected proper minor N   either has a proper internally 4-connected minor M^′$M^{\prime }$ with an N  -minor such that |E(M)−E(M^′)|?3$|E(M)-E(M^{\prime })|?3$ or has, up to duality, a triangle T and an element e of T   such that M\e$M\backslash e$ has an N-minor and has the property that one side of every 3-separation is a fan with at most four elements.     

Elements belonging to triangles in 3-connected matroids

An element e of a 3-connected matroid M is said to be superfluous provided M/e is 3-connected. In this paper, we show that a 3-connected matroid M with exactly k superfluous elements has at least

     

ContributionsOn binary k-paving matroids and Reed-Muller codes

A matroid M of rank r k is k-paving if all of its circuits have cardinality exceeding r − k. In this paper, we develop some basic results concerning k-paving matroids and their connections with codes. Also, we determine all binary 2-paving matroids.     

A revision and extension of results on 4-regular, 4-connected, claw-free graphs

In 1995, Plummer (1992) [6] published a paper in which he gave a characterization of 4-regular, 4-connected, claw-free graphs. Based on that work, Hartnell and Plummer (1996) [5] published a paper on 4-connected, claw-free, well-covered graphs a year later. However, in his 1995 paper, Plummer inadvertently omitted some of the graphs with odd order. In this paper, we will complete Plummer’s characterization of all 4-connected, 4-regular, claw-free graphs, and then show the implications this has on the well-covered graphs he and Hartnell determined. In addition, we will characterize 4-connected, 4-regular, claw-free, well-dominated graphs.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Edges not contained in triangles and the number of contractible edges in a 4-connected graph

Let G be a 4-connected graph, and let E_c(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have .     

A unique factorization theorem for matroids

We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra of a family of matroids that is closed under formation of minors and free products: namely, is cofree, cogenerated by the set of irreducible matroids belonging to .     

A combinatorial proof of a theorem of Freund

In 1989, Robert W. Freund published an article about generalizations of the Sperner lemma for triangulations of n-dimensional polytopes, when the vertices of the triangulations are labeled with points of Rn. For y∈Rn, the generalizations ensure, under various conditions, that there is at least one simplex containing y in the convex hull of its labels. Moreover, if y is generic, there is generally a parity assertion, which states that there is actually an odd number of such simplices.For one of these generalizations, contrary to the others, neither a combinatorial proof, nor the parity assertion were established. Freund asked whether a corresponding parity assertion could be true and proved combinatorially.The aim of this paper is to give a positive answer, using a technique which can be applied successfully to prove several results of this type in a very simple way. We prove actually a more general version of this theorem. This more general version was published by van der Laan, Talman and Yang in 2001, who proved it in a non-combinatorial way, without the parity assertion.     

A simplified completely positive reformulation for binary quadratic programs

In this paper, we propose a simplified completely positive programming reformulation for binary quadratic programs. The linear equality constraints associated with the binary constraints in the original problem can be aggregated into a single linear equality constraint without changing the feasible set of the classic completely positive reformulation proposed in the literature. We also show that the dual of the proposed simplified formulation is strictly feasible under a mild assumption.     

A Bombieri-type theorem for exponential sums

Let fk(n) be the characteristic function of n with Ω(n) = k,and Tk(x,α) =∑n≤xfk(n)e(nα).The main purpose of this paper is to establish a Bombieri-type mean-value theorem for Tk(x,α),via using the modified Huxley-Hooley contour and the large-sieve type zero-density estimate for Dirichlet L-functions.The result plays an important role in handling the enlarge major arcs when we try to solve the Waring-Goldbach type problem by the circle method.     

A general Isserlis theorem for mixed-Gaussian random variables

This work generalizes a widely used result derived by L. Isserlis for the expectations of products of jointly Gaussian random variables by extending it to include mixed-Gaussian random variables.     

A fixed point theorem for the infinite-dimensional simplex

We define the infinite-dimensional simplex to be the closure of the convex hull of the standard basis vectors in R^∞, and prove that this space has the fixed point property: any continuous function from the space into itself has a fixed point. Our proof is constructive, in the sense that it can be used to find an approximate fixed point; the proof relies on elementary analysis and Sperner's lemma. The fixed point theorem is shown to imply Schauder's fixed point theorem on infinite-dimensional compact convex subsets of normed spaces.     

Decision functions for chain classifiers based on Bayesian networks for multi-label classification

Multi-label classification problems require each instance to be assigned a subset of a defined set of labels. This problem is equivalent to finding a multi-valued decision function that predicts a vector of binary classes. In this paper we study the decision boundaries of two widely used approaches for building multi-label classifiers, when Bayesian network-augmented naive Bayes classifiers are used as base models: Binary relevance method and chain classifiers. In particular extending previous single-label results to multi-label chain classifiers, we find polynomial expressions for the multi-valued decision functions associated with these methods. We prove upper boundings on the expressive power of both methods and we prove that chain classifiers provide a more expressive model than the binary relevance method.