Long cycles in bipartite graphs

Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2.     

Short Cycle Structure of Graphs on Surfaces （1） -the Uniqueness Theorems

In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

2K2 vertex-set partition into nonempty parts

A graph is 2K₂-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K₂-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C₄-free graphs, circular-arc graphs, spiders, P₄-sparse graphs, and bipartite graphs the 2K₂-partition problem can be solved in polynomial time.     

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.     

Some isomorphisms between pairs of latin squares

Let A, B, C, D be latin squares with A orthogonal to B and C orthogonal to D. The pair A, B is isomorphic with the pair C, D if the graph of A, B is graph-isomorphic with the graph of C, D. A characterization is given for determining when a pair A, B of latin squares is isomorphic with a self-orthogonal square C and its transpose. Self-orthogonal squares are important because they are both abundant and easy to store. An algorithm either displays a self-orthogonal square C and an isomorphism from A, B to C, C^T or, if none exists, gives a small set of blocks to the existence of such a square isomorphism.     

On a graph related to permutability in finite groups

For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete.     

Further results on the reverse-order law

An explicit expression is obtained for a pair of generalized inverses (B^?,A^?) such that B^?A^?=(AB)⁺_MN, and a class of pairs (B^?,A^? of this property is shown. A necessary and sufficient condition for (AB)^? to have the expression B^?A^? is also given.     

Generalized inverse-positivity and splittings of M-matrices

The concepts of matrix monotonicity, generalized inverse-positivity and splittings are investigated and are used to characterize the class of all M-matrices A, extending the well-known property that A^?1?0 whenever A is nonsingular. These conditions are grouped into classes in order to identify those that are equivalent for arbitrary real matrices A. It is shown how the nonnegativity of a generalized left inverse of A plays a fundamental role in such characterizations, thereby extending recent work by one of the authors, by Meyer and Stadelmaier and by Rothblum. In addition, new characterizations are provided for the class of M-matrices with “property c”; that is, matrices A having a representation A=sI?B, s>0, B?0, where the powers of $\text{(}\text{1}\text{s}\text{)B}$ converge. Applications of these results to the study of iterative methods for solving arbitrary systems of linear equations are given elsewhere.     

A SURVEY OF THE ADDITIVE EIGENVALUE PROBLEM (WITH APPENDIX BY M. KAPOVICH)

The classical Hermitian eigenvalue problem addresses the following question: What are the possible eigenvalues of the sum A + B of two Hermitian matrices A and B, provided we fix the eigenvalues of A and B. A systematic study of this problem was initiated by H. Weyl (1912). By virtue of contributions from a long list of mathematicians, notably Weyl (1912), Horn (1962), Klyachko (1998) and Knutson–Tao (1999), the problem is finally settled. The solution asserts that the eigenvalues of A + B are given in terms of certain system of linear inequalities in the eigenvalues of A and B. These inequalities (called the Hom inequalities) are given explicitly in terms of certain triples of Schubert classes in the singular cohomology of Grassmannians and the standard cup product. Belkale (2001) gave a smaller set of inequalities for the problem in this case (which was shown to be optimal by Knutson–Tao–Woodward). The Hermitian eigenvalue problem has been extended by Berenstein–Sjamaar (2000) and Kapovich–Leeb–Millson (2009) for any semisimple complex algebraic group G. Their solution is again in terms of a system of linear inequalities obtained from certain triples of Schubert classes in the singular cohomology of the partial ag varieties G/P (P being a maximal parabolic subgroup) and the standard cup product. However, their solution is far from being optimal. In a joint work with P. Belkale, we define a deformation of the cup product in the cohomology of G/P and use this new product to generate our system of inequalities which solves the problem for any G optimally (as shown by Ressayre). This article is a survey (with more or less complete proofs) of this additive eigenvalue problem. The eigenvalue problem is equivalent to the saturated tensor product problem. We also give an extension of the saturated tensor product problem to the saturated restriction problem for any pair G ? ? of connected reductive algebraic groups. In the appendix by M. Kapovich, a connection between metric geometry and the representation theory of complex semisimple algebraic groups is explained. The connection runs through the theory of buildings. This connection is exploited to give a uniform (though not optimal) saturation factor for any G.     

Sign determinacy of M-matrix minors

We show that if A is an M-matrix for which the length of the longest simple cycle in its associated undirected graph G(A) is at most 3, then every minor of A has determined sign (nonnegative or nonpositive), independent of the magnitudes of the matrix entries. Consequently, if A and B are M-matrices such that G(A) and G(B) are subgraphs of an undirected graph with longest simple cycle at most 3, then all principal minors of AB are nonnegative.     

Classifying Hilbert bundles

A Hilbert bundle (p, B, X) is a type of fibre space p:B → X such that each fibre p^?1(x) is a Hilbert space. However, p^?1(x) may vary in dimension as x varies in X. We generalize the classical homotopy classification theory of vector bundles to a “homotopy” classification of certain Hilbert bundles. An (m, n)-bundle over the pair (X, A) is a Hilbert bundle (p, B, X) such that the dimension of p^?1(x) is m for x in A and n otherwise. The main result here is that if A is a compact set lying in the “edge” of the metric space X (e.g. if X is a topological manifold and A is a compact subset of the boundary of X), then the problem of classifying (m, n)-bundles over (X, A) reduces to a problem in the classical theory of vector bundles. In particular, we show there is a one-to-one correspondence between the members of the orbit set, [A, G_m($\text{C}$ⁿ)]/[X, U(n)] ¦ A, and the isomorphism classes of (m, n)-bundles over (X, A) which are trivial over X, A.     

Graphs Without Large Apples and the Maximum Weight Independent Set Problem

An apple A _k is the graph obtained from a chordless cycle C _k of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. The class of apple-free graphs is a common generalization of claw-free graphs and chordal graphs, two classes enjoying many attractive properties, including polynomial-time solvability of the maximum weight independent set problem. Recently, Brandstädt et al. showed that this property extends to the class of apple-free graphs. In the present paper, we study further generalization of this class called graphs without large apples: these are (A _k , A _k+1, . . .)-free graphs for values of k strictly greater than 4. The complexity of the maximum weight independent set problem is unknown even for k = 5. By exploring the structure of graphs without large apples, we discover a sufficient condition for claw-freeness of such graphs. We show that the condition is satisfied by bounded-degree and apex-minor-free graphs of sufficiently large tree-width. This implies an efficient solution to the maximum weight independent set problem for those graphs without large apples, which either have bounded vertex degree or exclude a fixed apex graph as a minor.     

A forbidden subgraph characterization of line-polar bipartite graphs

A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6].     

An exact algorithm for solving the vertex separator problem

Given G = (V, E) a connected undirected graph and a positive integer β(|V|), the vertex separator problem is to find a partition of V into no-empty three classes A, B, C such that there is no edge between A and B, max{|A|, |B|} ≤ β(|V|) and |C| is minimum. In this paper we consider the vertex separator problem from a polyhedral point of view. We introduce new classes of valid inequalities for the associated polyhedron. Using a natural lower bound for the optimal solution, we present successful computational experiments.     

Preservers of pairs of bivectors with bounded distance

We extend Liu’s fundamental theorem of the geometry of alternate matrices to the second exterior power of an infinite dimensional vector space and also use her theorem to characterize surjective mappings T from the vector space V of all n×n alternate matrices over a field with at least three elements onto itself such that for any pair A, B in V, rank(A-B)?2k if and only if rank(T(A)-T(B))?2k, where k is a fixed positive integer such that n?2k+2 and k?2.     

Antibandwidth and cyclic antibandwidth of meshes and hypercubes

The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle C_n, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth.     

Spin Leonard pairs

Let ${\mathbb K}$ denote a field, and let V denote a vector space over ${\mathbb K}$ of finite positive dimension. A pair A, A* of linear operators on V is said to be a Leonard pair on V whenever for each B∈{A, A*}, there exists a basis of V with respect to which the matrix representing B is diagonal and the matrix representing the other member of the pair is irreducible tridiagonal. A Leonard pair A, A* on V is said to be a spin Leonard pair whenever there exist invertible linear operators U, U* on V such that UA = A U, U*A* = A*U*, and UA* U ^?1 = U*^?1 AU*. In this case, we refer to U, U* as a Boltzmann pair for A, A*. We characterize the spin Leonard pairs. This characterization involves explicit formulas for the entries of the matrices that represent A and A* with respect to a particular basis. The formulas are expressed in terms of four algebraically independent parameters. We describe all Boltzmann pairs for a spin Leonard pair in terms of these parameters. We then describe all spin Leonard pairs associated with a given Boltzmann pair. We also describe the relationship between spin Leonard pairs and modular Leonard triples. We note a modular group action on each isomorphism class of spin Leonard pairs.     

Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.