Note – Uncrossing a Family of Set-Pairs

Frank and Jordán [1] proved an important min-max result on covering a crossing family of set-pairs. As an application, among others they can solve the unweighted node-connectivity augmentation problem for directed graphs in polynomial time. In this paper, we show how to solve the dual packing problem in polynomial time. To decompose a fractional dual optimum as a convex combination of integer vertices, besides the ellipsoid method, we use a polynomial-time algorithm for uncrossing a family of set-pairs. Our main result is this uncrossing algorithm. Received November 9, 1998 / Revised October 18, 1999     

Random Minimum Length Spanning Trees in Regular Graphs

r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998     

NOTE – On Minimizing Symmetric Set Functions

u, v ) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a ``max-back order' form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proof, here we show that the same algorithm works for an even more general class of set functions. Received December 16, 1998     

NOTE New Upper Bounds for a Canonical Ramsey Problem

f (l,k) be the minimum n with the property that every coloring yields either with , or with all distinct. We prove that if , then as . This supports the conjecture of Lefmann, R?dl, and Thomas that . Received July 2, 1998     

On the Single-Source Unsplittable Flow Problem

be a capacitated directed graph with a source s and k terminals with demands , . We would like to concurrently route every demand on a single path from s to the corresponding terminal without violating the capacities. There are several interesting and important variations of this unsplittable flow problem. If the necessary cut condition is satisfied, we show how to compute an unsplittable flow satisfying the demands such that the total flow through any edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, we therefore obtain an unsplittable flow with congestion at most 2, and this result is best possible. Furthermore, we show that all demands can be routed unsplittably in 5 rounds, i.e., all demands can be collectively satisfied by the union of 5 unsplittable flows. Finally, we show that 22.6% of the total demand can be satisfied unsplittably. These results are extended to the case when the cut condition is not necessarily satisfied. We derive a 2-approximation algorithm for congestion, a 5-approximation algorithm for the number of rounds and a -approximation algorithm for the maximum routable demand. Received: July 12, 1998     

A Bound on the Total Chromatic Number

. The proof is probabilistic. Received: November 26, 1996     

Bicliques in Graphs I: Bounds on Their Number

Bicliques are inclusion-maximal induced complete bipartite subgraphs in graphs. Upper bounds on the number of bicliques in bipartite graphs and general graphs are given. Then those classes of graphs where the number of bicliques is polynomial in the vertex number are characterized, provided the class is closed under induced subgraphs. Received January 27, 1997     

Ramsey Numbers for Trees of Small Maximum Degree

For a tree T we write and , , for the sizes of the vertex classes of T as a bipartite graph. It is shown that for T with maximum degree , the obvious lower bound for the Ramsey number R(T,T) of is asymptotically the correct value for R(T,T). Received December 15, 1999 RID=" " ID=" " The first and third authors were partially supported by NSERC. The second author was partially supported by KBN grant 2 P03A 021 17.     

Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks

n -vertex edge coloured graphs with multiplicity of Jordan blocks bounded by k can be done in time . Received: November 29, 1994     

Principally Unimodular Skew-Symmetric Matrices

principally unimodular (PU) if every principal submatrix has determinant 0 or ±1. Let A be a symmetric (0, 1)-matrix, with a zero diagonal. A PU-orientation of A is a skew-symmetric signing of A that is PU. If A′ is a PU-orientation of A, then, by a certain decomposition of A, we can construct every PU-orientation of A from A′. This construction is based on the fact that the PU-orientations of indecomposable matrices are unique up to negation and multiplication of certain rows and corresponding columns by −1. This generalizes the well-known result of Camion, that if a (0, 1)-matrix can be signed to be totally unimodular then the signing is unique up to multiplying certain rows and columns by −1. Camion's result is an easy but crucial step in proving Tutte's famous excluded minor characterization of totally unimodular matrices. Received: May 17, 1996     

An Extremal Problem For Random Graphs And The Number Of Graphs With Large Even-Girth

C _{2 k} -free subgraph of a random graph may have, obtaining best possible results for a range of p=p(n). Our estimates strengthen previous bounds of Füredi [12] and Haxell, Kohayakawa, and Łuczak [13]. Two main tools are used here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition; the second tool is the powerful result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] on uncrowded hypergraphs as given by Duke, Lefmann, and R?dl [7]. Received: February 17, 1995     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

The Distance-regular Graphs with Intersection Number and with an Eigenvalue

and with an eigenvalue . Received: October 2, 1995/Revised: Revised November 26, 1997     

NOTE – A Min-Max Relation for Monotone Path Systems in Simple Regions

xy -plane which bounds the simple polygonal (closed) region D. Let T and B be two finite, disjoint, equicardinal sets of points of D. We give a min-max relation for the maximum number of points of T and B which can be joined by a MPS in D, and a polytime algorithm for finding such a MPS. Received July 15, 1996/Revised October 7, 1999     

A Theorem of Truemper

Received November 5, 1997     

The Combinatorics of Biased Riffle Shuffles

Received: September 23, 1997     

A Lower Bound for the Translative Kissing Numbers of Simplices

H (K) of a d-dimensional convex body K is the maximum number of mutually non-overlapping translates of K that can be arranged so that all touch K. In this paper we show that holds for any d-dimensional simplex (). We also prove similar inequalities for some, more general classes of convex bodies. Received May 18, 1998     

A Bound for the Diameter of Distance-Regular Graphs

n vertices has diameter at most 5 logn. This essentially settles a problem of Brouwer, Cohen and Neumaier. Received: October 2, 1998