On the minor-minimal 3-connected matroids having a fixed minor

Let N be a minor of a 3-connected matroid M such that no proper 3-connected minor of M has N as a minor. This paper proves a bound on |E(M)−E(N)| that is sharp when N is connected.     

Constructing a 3-tree for a 3-connected matroid

In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M.     

On triangle-free 3-connected matroids

We present a method to construct any triangle-free 3-connected matroid starting from a matroid belonging to one of four infinite families and subsequently performing a sequence of small operations on it. This result extends to matroids a theorem proved by Kriesell for graphs.     

Minimally 3-connected isotropic systems

Isotropic systems are structures which unify some properties of 4-regular graphs and selfdual properties of binary matroids, such as connectivity and minors. In this paper, we find the minimally 3-connected isotropic systems. This result implies the binary part Tutte's wheels and whirls theorem.     

Capturing two elements in unavoidable minors of 3-connected binary matroids

Let M be a 3-connected binary matroid and let n   be an integer exceeding 2. Ding, Oporowski, Oxley, and Vertigan proved that there is an integer f(n)$f(n)$ so that if |E(M)|>f(n)$|E(M)|>f(n)$, then M has a minor isomorphic to one of the rank-n wheel, the rank-n   tipless binary spike, or the cycle or bond matroid of _K3,n$K_{3,n}$. This result was recently extended by Chun, Oxley, and Whittle to show that there is an integer g(n)$g(n)$ so that if |E(M)|>g(n)$|E(M)|>g(n)$ and x∈E(M)$x\in E(M)$, then x is an element of a minor of M isomorphic to one of the rank-n wheel, the rank-n   binary spike with a tip and a cotip, or the cycle or bond matroid of _K1,1,1,n$K_{1,1,1,n}$. In this paper, we prove that, for each i   in {2,3}$\{2,3\}$, there is an integer _hi(n)$h_i(n)$ so that if |E(M)|>_hi(n)$|E(M)|>h_i(n)$ and Z is an i-element rank-2 subset of M, then M has a minor from the last list whose ground set contains Z.     

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.     

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.     

The structure of the 4-separations in 4-connected matroids

For a 2-connected matroid M, Cunningham and Edmonds gave a tree decomposition that displays all of its 2-separations. When M is 3-connected, two 3-separations are equivalent if one can be obtained from the other by passing through a sequence of 3-separations each of which is obtained from its predecessor by moving a single element from one side of the 3-separation to the other. Oxley, Semple, and Whittle gave a tree decomposition that displays, up to this equivalence, all non-trivial 3-separations of M. Now let M be 4-connected. In this paper, we define two 4-separations of M to be 2-equivalent if one can be obtained from the other by passing through a sequence of 4-separations each obtained from its predecessor by moving at most two elements from one side of the 4-separation to the other. The main result of the paper proves that M has a tree decomposition that displays, up to 2-equivalence, all non-trivial 4-separations of M.     

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.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

On reid’s 3-simplicial matroid theorem

In this paper we prove the following result of Ralph Reid (which was never published nor completely proved). Theorem. Let M be a matroid coordinatizable (representable) over a prime field F. Then there is a 3-simplicial matroid M′ over F which is a series extension of M. The proof we give is different from the original proof of Reid which uses techniques of algebraic topology. Our proof is constructive and uses elementary matrix operations.     

Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method

In this article one discusses the controllability of a semi-discrete system obtained by discretizing in space the linear 1-D wave equation with a boundary control at one extremity. It is known that the semi-discrete models obtained with finite difference or the classical finite element method are not uniformly controllable as the discretization parameter h goes to zero (see [8]). Here we introduce a new semi-discrete model based on a mixed finite element method with two different basis functions for the position and velocity. We show that the controls obtained with these semi-discrete systems can be chosen uniformly bounded in L²(0,T) and in such a way that they converge to the HUM control of the continuous wave equation, i.e. the minimal L²-norm control. We illustrate the mathematical results with several numerical experiments. Supported by Grant BFM 2002-03345 of MCYT (Spain) and the TMR projects of the EU ``Homogenization and Multiple Scales" and ``New materials, adaptive systems and their nonlinearities: modelling, control and numerical simulations". Partially Supported by Grant BFM 2002-03345 of MCYT (Spain), Grant 17 of Egide-Brancusi Program and Grant 80/2005 of CNCSIS (Romania).     

Skew partial fields,multilinear representations of matroids,and a matrix tree theorem

We extend the notion of representation of a matroid to algebraic structures that we call skew partial fields. Our definition of such representations extends Tutte?s definition, using chain groups. We show how such representations behave under duality and minors, we extend Tutte?s representability criterion to this new class, and we study the generator matrices of the chain groups. An example shows that the class of matroids representable over a skew partial field properly contains the class of matroids representable over a skew field. Next, we show that every multilinear representation of a matroid can be seen as a representation over a skew partial field. Finally we study a class of matroids called quaternionic unimodular. We prove a generalization of the matrix tree theorem for this class.     

Some excluded-minor theorems for a class of polymatroids

Problems involving representability are among the most frequently studied of all the problems in matroid theory. This paper considers the corresponding class of problems for polymatroids. A polymatroidh on the setS is representable over a free matroid or is Boolean if there is a map fromS into the set of subsets of a setV which preserves rank, that is for all subsetsA ofS, . The class of Boolean polymatroids is minor-closed and in this paper we investigate the excluded minors of this class. In particular, we determine all such Boolean excluded minors that are 2-polymatroids.This research was partially supported by a grant from the Louisiana Education Quality Support Fund Through the Board of RegentsThis research was supported by a grant from the Commonwealth of Australia through the Australian Research Council     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Proof of a conjecture of Kahn for non-binary matroids

This note proves a conjecture of Kahn by showing that ifX is a 3-element independent set in a 3-connected non-binary matroid M, thenM has a connected non-binary minor havingX as a basis. This research was partially supported by an LSU Summer Research Grant.     

Multiple solutions for quasilinear elliptic equations with a finite potential well

We consider multiplicity of solutions for a class of quasilinear problems which has received considerable attention in the past, including the so called Modified Nonlinear Schrödinger Equations. By combining a new variational approach via q-Laplacian regularization and the compactness arguments from [4] we establish infinitely many bound state solutions for the quasilinear Schrödinger type equations, extending the earlier work of [4] for semilinear equations.     

Quasianalytic and nonquasianalytic solutions for a class of weakly hyperbolic Cauchy problems

In the weakly hyperbolic Cauchy problem, we investigate the relation between the modulus of continuity in the time variable of the coefficients and the well-posedness in Beurling-Roumieu classes of ultradifferentiable functions and functionals. We find a sharp condition on the modulus of continuity assuring the well-posedness in nonquasianalytic classes.