Drawing Trees with Perfect Angular Resolution and Polynomial Area

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node $v$ equal to $2\pi /d(v)$ . We show:

1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area.
2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution.
3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area.

Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.     

The Critical Group of a Line Graph

The critical group of a graph is a finite abelian group whose order is the number of spanning forests of the graph. This paper provides three basic structural results on the critical group of a line graph.

• The first deals with connected graphs containing no cut-edge. Here the number of independent cycles in the graph, which is known to bound the number of generators for the critical group of the graph, is shown also to bound the number of generators for the critical group of its line graph.

• The second gives, for each prime p, a constraint on the p-primary structure of the critical group, based on the largest power of p dividing all sums of degrees of two adjacent vertices.

• The third deals with connected graphs whose line graph is regular. Here known results relating the number of spanning trees of the graph and of its line graph are sharpened to exact sequences which relate their critical groups.

The first two results interact extremely well with the third. For example, they imply that in a regular nonbipartite graph, the critical group of the graph and that of its line graph determine each other uniquely in a simple fashion.     

The shortest augmenting path method for solving assignment problems — Motivation and computational experience

In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect:

we introduce this basic concept using matching theory

we present several efficient labeling techniques for constructing shortest augmenting paths

we show the relationship of this approach to several classical assignment algorithms

we present extensive computational experience for complete problems, and

we show how postoptimal analysis can be performed using this approach and naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems

     

A spectral approach to polyhedral dimension

Thespectrum spec( ) of a convex polytope is defined as the ordered (non-increasing) list of squared singular values of [A|1], where the rows ofA are the extreme points of . The number of non-zeros in spec( ) exceeds the dimension of by one. Hence, the dimension of a polytope can be established by determining its spectrum. Indeed, this provides a new method for establishing the dimension of a polytope, as the spectrum of a polytope can be established without appealing to a direct proof of its dimension. The spectrum is determined for the four families of polytopes defined as the convex hulls of:

1. The edge-incidence vectors of cutsets induced by balanced bipartitions of the vertices in the complete undirected graph on 2_q vertices (see Section 6).
2. The edge-incidence vectors of Hamiltonian tours in the complete undirected graph onn vertices (see Section 6).
3. The arc-incidence vectors of directed Hamiltonian tours in the complete directed graph ofn nodes (see Section 7).
4. The edge-incidence vectors of perfect matchings in the complete 3-uniform hypergraph on 3_q vertices (see Section 8).

In the cases of (ii) and (iii), the associated dimension results are well-known. The dimension results for (i) and (iv) do not seem to be well-known. General principles are discussed for ‘balanced polytopes’ arising from complete structures.     

On the “log rank”-conjecture in communication complexity

We show the existence of a non-constant gap between the communication complexity of a function and the logarithm of the rank of its input matrix. We consider the following problem: each of two players gets a perfect matching between twon-element sets of vertices. Their goal is to decide whether or not the union of the two matcliings forms a Hamiltonian cycle. We prove:

1. The rank of the input matrix over the reals for this problem is 2 ^O(n) .
2. The non-deterministic communication complexity of the problem is Ω(nloglogn).

Our result also supplies a superpolynomial gap between the chromatic number of a graph and the rank of its adjacency matrix. Another conclusion from the second result is an Ω(nloglogn) lower bound for the graph connectivity problem in the non-deterministic case. We make use of the theory of group representations for the first result. The second result is proved by an information theoretic argument.     

On optimal realizations of finite metric spaces by graphs

Graph realizations of finite metric spaces have widespread applications, for example, in biology, economics, and information theory. The main results of this paper are:

1. Finding optimal realizations of integral metrics (which means all distances are integral) is NP-complete.
2. There exist metric spaces with a continuum of optimal realizations.

Furthermore, two conditions necessary for a weighted graph to be an optimal realization are given and an extremal problem arising in connection with the realization problem is investigated.     

Standard completions for quasiordered sets

A standard completion for a quasiordered set Q is a closure system whose point closures are the principal ideals of Q. We characterize the following types of standard completions by means of their closure operators:

1. V-distributive completions,
2. Completely distributive completions,
3. A-completions (i.e. standard completions which are completely distributive algebraic lattices),
4. Boolean completions.

Moreover, completely distributive completions are described by certain idempotent relations, and the A-completions are shown to be in one-to-one correspondence with the join-dense subsets of Q. If a pseudocomplemented meet-semilattice Q has a Boolean completion ?, then Q must be a Boolean lattice and ? its MacNeille completion.     

Solving matching problems with linear programming

In this paper we describe an implementation of a cutting plane algorithm for the perfect matching problem which is based on the simplex method. The algorithm has the following features:

-It works on very sparse subgraphs ofK _n which are determined heuristically, global optimality is checked using the reduced cost criterion.

-Cutting plane recognition is usually accomplished by heuristics. Only if these fail, the Padberg-Rao procedure is invoked to guarantee finite convergence.

Our computational study shows that—on the average—very few variables and very few cutting planes suffice to find a globally optimal solution. We could solve this way matching problems on complete graphs with up to 1000 nodes. Moreover, it turned out that our cutting plane algorithm is competitive with the fast combinatorial matching algorithms known to date.     

Packing seagulls

A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if

1. |V (G)|≥3k
2. G is k-connected
3. for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
4. the complement graph of G has a matching with k edges.

We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Elementary Abelianp-extensions of algebraic function fields

LetK be a field of characteristicp>0 andF/K be an algebraic function field. We obtain several results on Galois extensionsE/F with an elementary Abelian Galois group of orderp ⁿ.

1. E can be generated overF by some elementy whose minimal polynomial has the specific formT ^pn?T?z.
2. A formula for the genus ofE is given.
3. IfK is finite, then the genus ofE grows much faster than the number of rational points (as [E∶F] → ∞).
4. We present a new example of a function fieldE/K whose gap numbers are nonclassical.

     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

Multidimensional symmetric stable processes

This paper surveys recent remarkable progress in the study of potential theory for symmetric stable processes. It also contains new results on the two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric α-stable process in boundedC ^1,1 open sets. The new results give explicit information on how the comparing constants depend on parameter α and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing α ↑ 2. In addition to these new estimates, this paper surveys recent progress in the study of notions of harmonicity, integral representation of harmonic functions, boundary Harnack inequality, conditional gauge and intrinsic ultracontractivity for symmetric stable processes. Here is a table of contents.

1. Introduction
2. Green function and Poisson kernel estimates

1. Estimates on balls
2. Estimates on boundedC ^1,1 domains
3. Estimates on boundedC ^1,1 open sets

1. Harmonic functions and integral representation
2. Two notions of harmonicity
3. Martin kernel and Martin boundary
4. Integral representation and uniqueness
5. Boundary Harnack principle
6. Conditional process and its limiting behavior
7. Conditional gauge and intrinsic ultracontractivity

     

Laguerre-Ebenen mit Symmetrien an Punktepaaren und Zykeln

Let ∞ be a point of a Laguerre plane, such that

1. For any cycle containing ∞ there exists an automorphism of order 2 whose set of fixed points is exactly z.
2. For any point X, not parallel to ∞, there exists an automorphism of order 2 whose set of fixed points is exactly {∞,X}.

Then the give Laguerre plane is a Miquelian one of characteristik ≠ 2.     

Flow of a weakly ionized gas between parallel cold walls with parabolic velocity profile

Ambipolar diffusion between flat cold insulating walls of a weakly ionized gas which flows in the direction parallel to the walls with parabolic velocity profile is investigated theoretically. It has been found that:

1. the patched velocity of linear and nonlinear regions tends to 1/√2 of the thermal velocity;
2. the thickness of the nonlinear region with parabolic velocity profile is found to be less than that of Shioda who considered uniform streaming (J. Phys. Soc. Japan, 1969,29, 197); and
3. the number density and the electric potential approximations in the sheath edge do not depend uponx, the coordinate in the streaming direction.

     

On a class of σ-space with special nets

Strong CP(HCP)-netted spaces are defined and some properties are shown. In particular, the following results are shown.

1. A submetrizable space is strong CP(HCP)-netted provided that the space admits a perfect map onto a strong CP(HCP)-netted space.
2. The image of a strong CP(HCP)-netted space under a perfect map is strong CP(HCP)-netted space.
3. A stratifiable space is strong HCP-netted if the space has a countable closed cover consisting of strong HCP-netted subspaces.

     

Parametric nonlinear discrete optimization over well-described sets and matroid intersections

We address optimization of parametric nonlinear functions of the form f(Wx), where ${f : \mathbb {R}^d \rightarrow \mathbb {R}}$ is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set ${\mathcal {F}}$ of integer points in ${\mathbb {R}^n}$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f, W and ${\mathcal {F}}$ . One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W. Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that ${\mathcal {F}}$ is well described (i.e., we can efficiently optimize a linear objective function on ${\mathcal {F}}$ ; equivalently, we have an efficient separation oracle for the convex hull of ${\mathcal {F}}$ ). For example, the sets of characteristic vectors of (i) matchings of a graph, and (ii) common bases of a pair of matroids on a common ground set satisfy this property. In this setting, the problem is already known to be intractable (even for a single matroid), for general f (given by a comparison oracle), for (i) d = 1 and binary-encoded W, and for (ii) d = n and W = I. Our main results (a few technicalities and some generality suppressed):

1. When ${\mathcal {F}}$ is well described, f is convex (or even quasi-convex), and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization.

1. When ${\mathcal {F}}$ is well described, f is a norm, and W is binary-encoded, we give an efficient deterministic constant-approximation algorithm for maximization (Note that the approximation factor depends on the norm, and hence implicitly on the number of rows of W, while the running time increases only linearly in the number of rows of W).

1. When non-negative ${\mathcal {F}}$ is well described, f is “ray concave” and non-decreasing, and non-negative W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization.

1. When ${\mathcal {F}}$ is the set of characteristic vectors of common independent sets or bases of a pair of rational vectorial matroids on a common ground set, f is arbitrary, and W has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.

     

Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

Every 4k-edge-connected graph is Weakly 3k-linked

We prove:

1. Fork ≥ 2 andα = 0, 1, every (4k + 2α)-edge-connected graph is weakly (3k + 2α)-linked.
2. IfG is ak-edge-connected graph (k ≥ 2),s, t are vertices andf is an edge, then there exists a pathP betweens andt such thatf ? E(P) andG ? E(P) ? f is (k ? 2)-edge-connected, whereE(P) denotes the edge set ofP.