A p-adic analogue of Siegel's theorem on sums of squares

Siegel proved that every totally positive element of a number field K is the sum of four squares, so in particular the Pythagoras number is uniformly bounded across number fields. The p-adic Kochen operator provides a p-adic analogue of squaring, and a certain localisation of the ring generated by this operator consists of precisely the totally p-integral elements of K. We use this to formulate and prove a p-adic analogue of Siegel's theorem, by introducing the p-Pythagoras number of a general field, and showing that this number is uniformly bounded across number fields. We also generally study fields with finite p-Pythagoras number and show that the growth of the p-Pythagoras number in finite extensions is bounded.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

The Number of M-Sequences and f-Vectors

M -sequences (a.k.a. f-vectors for multicomplexes or O-sequences) in terms of the number of variables and a maximum degree. In particular, it is shown that the number of M-sequences for at most 2 variables are powers of two and for at most 3 variables are Bell numbers. We give an asymptotic estimate of the number of M-sequences when the number of variables is fixed. This leads to a new lower bound for the number of polytopes with few vertices. We also prove a similar recursive formula for the number of f-vectors for simplicial complexes. Keeping the maximum degree fixed we get the number of M-sequences and the number of f-vectors for simplicial complexes as polynomials in the number of variables and it is shown that these numbers are asymptotically equal. Received: February 28, 1996/Revised: February 26, 1998     

Copositive programming motivated bounds on the stability and the chromatic numbers

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

Structural properties and stochastic bounds for a buffer problem in packetized voice transmission

We consider a communication channel which carries packetized voice. A fixed number (K) of calls are being transmitted. Each of these calls generates one packet at everyC timeslots and the channel can transmit at most one packet every timeslot. We consider the nontrivial caseK ≤C. We study the effectsK, C and the arrival process have on the number of packets in the buffer. When the call origination epochs in the firstC timeslots of theK calls are uniformly distributed (i.e. when the arrivals during the firstC timeslots have a multinomial distribution) it is shown that the stationary number of calls waiting in the buffer is stochastically increasing and convex in the number of calls. For a fixed average number of calls per slot, it is shown that increasing the number of slots per frame increases the stationary number of packets in the buffer in the sense of increasing convex ordering. Using this, it is shown that the stationary number of packets in the buffer is bounded from above by the number of packets in a stationary discreteM/D/1 queue with arrival rateK/C and unit service time. This bound is in the sense of the increasing convex order.     

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

On the Pseudolinear Crossing Number

A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph.     

Colorings and orientations of graphs

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant.     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

Extension of Turán's Theorem to the 2-Stability Number

 Given a graph G with n vertices and stability number α(G), Turán's Theorem gives a lower bound on the number of edges in G. Furthermore, Turán has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α₂(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α₂(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's Theorem to the q-stability number, for q>2. Received: July 21, 1999 Final version received: August 22, 2000 Present address: GERAD, 3000 ch. de la Cote-Ste-Catherine, Montreal, Quebec H3T 2A7, Canada. e-mail: Alain.Hertz@gerad.ca     

Higher relative class number formulae

Let E be a totally complex abelian number field with maximal real subfield F, and let denote the non-trivial character of . Similar to the classical case n=1 the value of the Artin L-function at for odd is given by a relative class number formula of the form Here is a higher Q-index, which is equal to 1 or 2 and is a higher relative class number. Here for any number field L the higher class number is the order of the finite group closely related to the order of the higher K-theory group of the ring of integers in L. Received: 4 June 1999 / Revised version: 27 September 2001 / Published online: 26 April 2002     

Which Crossing Number Is It Anyway?

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the largest of these numbers (the crossing number) cannot exceed, twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E₀ be a subset of its edges such that there is a drawing of G, in which every edge belonging to E₀ crosses any other edge an even number of times. Then g can be redrawn so that the elements of E₀ are not involved in any crossing. Finally, we show that the determination of each of these parameters is an NP-hard problem and it is NP-complete in the case of the crossing number and the odd-crossing number.     

The splitting number of the complete graph

If a given graphG can be obtained bys vertex identifications from a suitable planar graph ands is the minimum number for which this is possible thens is called the splitting number ofG. Here a formula for the splitting number of the complete graph is derived.     

The distinguishing number of the direct product and wreath product action

Let G be a group acting faithfully on a set X. The distinguishing number of the action of G on X, denoted D _G(X), is the smallest number of colors such that there exists a coloring of X where no nontrivial group element induces a color-preserving permutation of X. In this paper, we consider the distinguishing number of two important product actions, the wreath product and the direct product. Given groups G and H acting on sets X and Y respectively, we characterize the distinguishing number of the wreath product G ≀_Y H in terms of the number of distinguishing colorings of X with respect to G and the distinguishing number of the action of H on Y. We also prove a recursive formula for the distinguishing number of the action of the Cartesian product of two symmetric groups S _m × S _n on [m] × [n].     

Obstacle Numbers of Graphs

An obstacle representation of a graph G is a drawing of G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles, such that an edge exists in G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of G is the smallest number of obstacles (convex obstacles) in any obstacle representation of G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex k-gon if and only if it is a circular arc graph with clique covering number at most k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with a single segment obstacle if and only if it is the complement of an interval bigraph.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

On the regulation number of a multigraph

The regulation number of a multigraphG having maximum degreed is the minimum number of additional vertices that are required to construct ad-regular supermultigraph ofG. It is shown that the regulation number of any multigraph is at most 3. The regulation number of a multidigraph is defined analogously and is shown never to exceed 2. A multigraphG has strengthm if every two distinct vertices ofG are joined by at mostm parallel edges. For a multigraphG of strengthm and maximum degreed, them-regulation number ofG is the minimum number of additional vertices that are required to construct ad-regular supermultigraph ofG having strengthm. A sharp upper bound on the 2-regulation number of a multigraph is shown to be (d+5)/2, and a conjecture for generalm is presented. Research supported by a Western Michigan University faculty research fellowship. Research Professor of Electrical Engineering and Computer Science, Stevens Institute, Hoboken, NJ and Visiting Scholar, Courant Institute, New York University, Spring 1984. Research supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

The Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs

We prove that the Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs can be solved by an algorithm requiring a number of elementary operations and a number of evaluations of the nonlinear cost functions which are both bounded by polynomials inr, n, m, wherer is the number of nodes,n is the number of arcs andm the number of sinks in the network.On leave from Institute of Mathematics, P.O. Box 631, Bo Ho, Hanoi, Vietnam.     

Rotation numbers and moduli of elliptic curves

Given a circle diffeomorphism f, we can construct a map taking each real number a to the rotation number of the diffeomorphism f +a. In 1978, V. I. Arnold suggested a complex analog To this map. Given a complex number z with Im z > 0, Arnold used the map f + z to construct an elliptic curve. The moduli map takes every number z to the modulus μ(z) of this elliptic curve.     

A combinatorial perspective on the Radon convexity theorem

Matroid-theoretic methods are employed to compute the number of complementary subsets of points of a set S whose convex hulls intersect (a number Radon proved to be nonzero when S has an affine dependency). This number is shown to be an invariant only of the dependence structure of S. Strict bounds are given depending on the cardinality and dimension of S and the number is related to other matroid invariants.