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.     

The structure of the 3-separations of 3-connected matroids

Tutte defined a k-separation of a matroid M to be a partition (A,B) of the ground set of M such that |A|,|B|k and r(A)+r(B)−r(M)<k. If, for all m<n, the matroid M has no m-separations, then M is n-connected. Earlier, Whitney showed that (A,B) is a 1-separation of M if and only if A is a union of 2-connected components of M. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. When M is 3-connected, this paper describes a tree decomposition of M that displays, up to a certain natural equivalence, all non-trivial 3-separations of M.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.     

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.     

Connected matroids with a small circumference

Lemos and Oxley proved that if M is a connected matroid with |E(M)|⩾3r(M), then M has a circuit C such that M⧹C is connected. In this paper, we shall improve this result proving that for a simple and connected matroid M, if r(M)⩾7 and |E(M)|⩾3r(M)−3, then M has a circuit C such that M⧹C is connected. To prove this result, we shall construct all the connected matroids having circumference at most five, with the exception of those which are 3-connected and have rank five.     

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.     

Conjugacy problem in groups of oriented geometrizable 3-manifolds

The aim of this paper is to show that the fundamental group of an oriented 3-manifold which satisfies Thurston's geometrization conjecture has a solvable conjugacy problem. In other words, for any such 3-manifold M, there exists an algorithm which can decide for any couple of elements u,v of π₁(M) whether u and v are in the same conjugacy class of π₁(M) or not. More topologically, the algorithm decides for any two loops in M, whether they are freely homotopic or not.     

The fundamental Gray 3-groupoid of a smooth manifold and local 3-dimensional holonomy based on a 2-crossed module

We define the thin fundamental Gray 3-groupoid S₃(M) of a smooth manifold M and define (by using differential geometric data) 3-dimensional holonomies, to be smooth strict Gray 3-groupoid maps S₃(M)→C(H), where H is a 2-crossed module of Lie groups and C(H) is the Gray 3-groupoid naturally constructed from H. As an application, we define Wilson 3-sphere observables.     

Complexity of a 3-dimensional assignment problem

We show that a certain 3-dimensional assignment problem is NP-complete. To do this we show that the following problem is NP-complete: given bipartite graphs G₁, G₂ with the same sets of vertices, do there exist perfect matchings M₁, M₂ of G₁, G₂ respectively such that M₁ ∩ M₂ =Ø?     

Eigenvalue assignments and the two largest multiplicities in a Hermitian matrix whose graph is a tree

Among the possible multiplicity lists for the eigenvalues of Hermitian matrices whose graph is a tree we focus upon M₂, the maximum value of the sum of the two largest multiplicities. The corresponding M₁ is already understood. The notion of assignment (of eigenvalues to subtrees) is formalized and applied. Using these ideas, simple upper and lower bounds are given for M₂ (in terms of simple graph theoretic parameters), cases of equality are indicated, and a combinatorial algorithm is given to compute M₂ precisely. In the process, several techniques are developed that likely have more general uses.     

Finding a small 3-connected minor maintaining a fixed minor and a fixed element

LetN andM be 3-connected matroids, whereN is a minor ofM on at least 4 elements, and lete be an element ofM and not ofN. Then, there exists a 3-connected minor \(\bar M\) ofM that usese, hasN as a minor, and has at most 4 elements more thanN. This result generalizes a theorem of Truemper and can be used to prove Seymour’s 2-roundedness theorem, as well as a result of Oxley on triples in nonbinary matroids.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.     

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

     

High distance Heegaard splittings of 3-manifolds

J. Hempel [J. Hempel, 3-manifolds as viewed from the curve complex, Topology 40 (3) (2001) 631-657] used the curve complex associated to the Heegaard surface of a splitting of a 3-manifold to study its complexity. He introduced the distance of a Heegaard splitting as the distance between two subsets of the curve complex associated to the handlebodies. Inspired by a construction of T. Kobayashi [T. Kobayashi, Casson-Gordon's rectangle condition of Heegaard diagrams and incompressible tori in 3-manifolds, Osaka J. Math. 25 (3) (1988) 553-573], J. Hempel [J. Hempel, 3-manifolds as viewed from the curve complex, Topology 40 (3) (2001) 631-657] proved the existence of arbitrarily high distance Heegaard splittings.In this work we explicitly define an infinite sequence of 3-manifolds {Mn} via their representative Heegaard diagrams by iterating a 2-fold Dehn twist operator. Using purely combinatorial techniques we are able to prove that the distance of the Heegaard splitting of Mn is at least n.Moreover, we show that π₁(Mn) surjects onto π₁(Mn−1). Hence, if we assume that M⁰ has nontrivial boundary then it follows that the first Betti number β₁(Mn)>0 for all n?1. Therefore, the sequence {Mn} consists of Haken 3-manifolds for n?1 and hyperbolizable 3-manifolds for n?3.     

Moves for standard skeleta of 3-manifolds with marked boundary

A 3-manifold with marked boundary is a pair (M, X), where M is a compact 3-manifold whose (possibly empty) boundary is made up of tori and Klein bottles, and X is a trivalent graph that is a spine of ?M. A standard skeleton of a 3-manifold with marked boundary (M, X) is a standard sub-polyhedron P of M such that P ?? ?M coincides with X and with ?P, and such that ${P \cup \partial M}$ is a spine of ${M\setminus B}$ (where B is a ball). In this paper, we will prove that the classical set of moves for standard spines of 3-manifolds (i.e. the MP-move and the V-move) does not suffice to relate to each other any two standard skeleta of a 3-manifold with marked boundary. We will also describe a condition on the 3-manifold with marked boundary that allows to establish whether the generalised set of moves, made up of the MP-move and the L-move, suffices to relate to each other any two standard skeleta of the 3-manifold with marked boundary. For the 3-manifolds with marked boundary that do not fulfil this condition, we give three other moves: the CR-move, the T₁-move and the T₂-move. The first one is local and, with the MP-move and the L-move, suffices to relate to each other any two standard skeleta of a 3-manifold with marked boundary fulfilling another condition. For the universal case, we will prove that the non-local T₁-move and T₂-move, with the MP-move and the L-move, suffice to relate to each other any two standard skeleta of a generic 3-manifold with marked boundary. As a corollary, we will get that disc-replacements suffice to relate to each other any two standard skeleta of a 3-manifold with marked boundary.     

Pre-Bloch invariants of 3-manifolds with boundary

Let M be an oriented hyperbolic 3-manifold with finite volume. In [W.D. Neumann, J. Yang, Bloch invariants of hyperbolic 3-manifolds, Duke Math. J. 96 (1999) 29-59. [9]], Neumann and Yang defined an element β(M) of Bloch group B(C) for M. For this β(M), volume and Chern-Simons invariant of M is represented by a transcendental function. In this paper, we define β(M,ρ,C,o)∈P(C) for an oriented 3-manifold M with boundary, a representation of its fundamental group , a pants decomposition C of ∂M and an orientation o on simple closed curves of C. Unlike in the case of finite volume, we construct an element of pre-Bloch group P(C), and we need essentially the pants decomposition on the boundary. The volume makes sense for β(M,ρ,C,o) and we can describe the variation of volume on the deformation space.     

Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

A spanning tree T of a graph G is called a treet-spanner, if the distance between any two vertices in T is at most t-times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81-87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203-210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.     

Generalized knight’s tour on 3D chessboards

In [G.L. Chia, Siew-Hui Ong, Generalized knight’s tours on rectangular chessboards, Discrete Applied Mathematics 150 (2005) 80-98], Chia and Ong proposed the notion of the generalized knight’s tour problem (GKTP). In this paper, we address the 3D GKTP, that is, the GKTP on 3D chessboards of size L×M×N, where L≤M≤N. We begin by presenting several sufficient conditions for a 3D chessboard not to admit a closed or open generalized knight’s tour (GKT) with given move patterns. Then, we turn our attention to the 3D GKTP with (1, 2, 2) move. First, we show that a chessboard of size L×M×N does not have a closed GKT if either (a) L≤2 or L=4, or (b) L=3 and M≤7. Then, we constructively prove that a chessboard of size 3×4s×4t with s≥2and t≥2 must contain a closed GKT.     

2 D n (3)(9≤n=2 m +1 not a prime) can be characterized by its order components

In this paper we prove that ifG is a finite group,² D _n (3)(9≤n=2 ^m +1 not a prime),G andM have the same order components, thenG ≈= M.