Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

Perturbation of the Laplacian by the Coulomb potential and a point interaction in L p (ℝ)3

Perturbations of -+/|x| (with >0) by a point interaction centered at zero are defined in L ^p(³). This is done for 3/20 (³{0}), such that the extension is the negative generator of an analytic semigroup on L ^p(³).     

Star arboricity

Astar forest is a forest all of whose components are stars. Thestar arboricity, st(G) of a graphG is the minimum number of star forests whose union covers all the edges ofG. Thearboricity, A(G), of a graphG is the minimum number of forests whose union covers all the edges ofG. Clearlyst(G)A(G). In fact, Algor and Alon have given examples which show that in some casesst(G) can be as large asA(G)+(log) (where is the maximum degree of a vertex inG). We show that for any graphG, st(G)A(G)+O(log).     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.     

The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

Inequalities in Products of Minors of Totally Nonnegative Matrices

Let _I,I be the minor of a matrix which corresponds to row set I and column set I. We give a characterization of the inequalities of the form _{I,I K,K J,J L,L} which hold for all totally nonnegative matrices. This generalizes a recent result of Fallat, Gekhtman, and Johnson.     

Parabelscharen und grenzkreise in der isotropen ebene

It is known by H. Sachs [5] that the classical curve theorem of ABRAMESCU also holds in isotropic geometry. Generalising an idea due to O. Röschel [2] we regard all inscribed parabolas (s, t) of a triangle (t). This triangle is formed by the tangents of three neighbouring points of a C -curve k(t) in an isotropic plane. Let U((t)) be the circumcircle of (t) and I((t)) the incircle of the triangle (t) whose midpoints of the sides are the vertices of (t). The circle U((t)) is the locus of the isotropic focal points of (s, t) and the incircle I((T)) the envelope of the isotropic axes of (s, t). We prove that the ABRAMESU-circle — lim U((t)) — is identical with the locus of the focal points of lim (s, t) and the circle lim I((t)) with the envelope of the axes of lim (s, t). The characteristic points, different from k(t), of the circles lim U((t)) and lim I((t)) determine the direction of the affine-normal of k(t).Herrn Professor Helmut Mäurer zum 60. Geburtstag gewidmet     

Uniqueness in some higher order elliptic boundary value problems

Summary The uniqueness of the solution to two boundary value problems for the linear equation ³ u –a ² u +b u –cu =F and to two boundary value problems for the quasilinear differential equation ² u +w(u) =f are proved. The proofs follow as a consequence of maximum principles for a functional which is defined on solutions to the differential equation.

---

Zusammenfassung Die Eindeutigkeit der Lösung zweier Randwertaufgaben für die lineare Gleichung ³ u –a ² u +b u –cu =F und zweier Randwertaufgaben für die quasilineare Differentialgleichung ² u +w(u) =f wird bewiesen. Der Beweis folgt aus einem Maximumprinzip für ein Funktional, das für die Lösungen der Gleichung definiert ist.

     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

Bases for Splines on a Subdivided Domain

Let S^r() be the module of all splines of smoothness r on the rectilinear partition which subdivides some domain D. Further, let S^r() be the module of all splines of smoothness r on which also subdivides D, where is a finer subdivision of . We study the relationship between a generating set of S^r() and a generating set for S^r(). This paper gives an algorithm for extending a generating set for S^r() to one for for S^r(). This method is built on algebraic properties of splines and the Gröbner Basis Algorithm.     

Extremal problems of Bloch function spaces

Letf be analytic in a hyperbolic region . The Bloch constant _f off is defined by , where (z)|dz| is the Poincaré metric in . Suppose is hyperbolic and where . Then for allf withf() , we have _f 1/(). In this paper we study the extremal functions defined by _f =1/() and the existence of those functions.Supported by the National Natural Science Foundation of China.     

Optimal growth rates for a viscous Hamilton-Jacobi equation

The growth of the L^m-norm, m [1,], of non-negative solutions to the Cauchy problem _t u – u = |u| is studied for non-negative initial data decaying at infinity. More precisely, the function is shown to be bounded from above and from below by positive real numbers. This result indicates an asymptotic behaviour dominated by the hyperbolic Hamilton-Jacobi term of the equation. A one-sided estimate for ln u is also established.     

Proof of a Conjecture of Bollobás and Eldridge for Graphs of Maximum Degree Three*

Let G ₁ and G ₂ be simple graphs on n vertices. If there are edge-disjoint copies of G ₁ and G ₂ in K _n , then we say there is a packing of G ₁ and G ₂. A conjecture of Bollobás and Eldridge [5] asserts that if ((G ₁)+1) ((G ₂)+1) n + 1 then there is a packing of G ₁ and G ₂. We prove this conjecture when (G ₁) = 3, for sufficiently large n.* This work was supported in part by a grant from National Science Foundation (DMS-9801396). Partially supported by OTKA T034475. Part of this work was done while the authors were graduate students at Rutgers University; Research partially supported by a DIMACS fellowship.     

Local Recognition Of Non-Incident Point-Hyperplane Graphs

Let be a projective space. By H() we denote the graph whose vertices are the non-incident point-hyperplane pairs of , two vertices (p,H) and (q,I) being adjacent if and only if p I and q H. In this paper we give a characterization of the graph H() (as well as of some related graphs) by its local structure. We apply this result by two characterizations of groups G with PSL _n ( )GPGL _n ( ), by properties of centralizers of some (generalized) reflections. Here is the (skew) field of coordinates of .     

Iterated Homology of Simplicial Complexes

We develop an iterated homology theory for simplicial complexes. Thistheory is a variation on one due to Kalai. For a simplicial complex of dimension d – 1, and each r = 0, ...,d, we define rth iterated homology groups of . When r = 0, this corresponds to ordinary homology. If is a cone over , then when r = 1, we get the homology of . If a simplicial complex is (nonpure) shellable, then its iterated Betti numbers give the restriction numbers, h _k,j , of the shelling. Iterated Betti numbers are preserved by algebraic shifting, and may be interpreted combinatorially in terms of the algebraically shifted complex in several ways. In addition, the depth of a simplicial complex can be characterized in terms of its iterated Betti numbers.     

Groups acting simply transitively on the vertices of a building of typeà 2, I

If a group acts simply transitively on the vertices of an affine building with connected diagram, then must be of typeà _n–1 for somen2, and must have a presentation of a simple type. The casen=2, when is a tree, has been studied in detail. We consider the casen=3, motivated particularly by the case when is the building ofG=PGL(3,K),K a local field, and when G. We exhibit such a group whenK=F _q ((X)),q any prime power. Our study leads to combinatorial objects which we calltriangle presentations. These triangle presentations give rise to some new buildings of typeà ₂.     

Almost Covers Of 2-Arc Transitive Graphs

Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case K _v+1 is covered by results of Gardiner and Praeger. We consider here the general case where K _v+1, and prove that, for some even integer n 4, is a near n-gonal graph with respect to a certain G-orbit on n-cycles of . Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .)     

The Laplacian with Robin Boundary Conditions on Arbitrary Domains

Using a capacity approach, we prove in this article that it is always possible to define a realization of the Laplacian on L ²() with generalized Robin boundary conditions where is an arbitrary open subset of R ⁿ and is a Borel measure on the boundary of . This operator generates a sub-Markovian C ₀-semigroup on L ²(). If d=d where is a strictly positive bounded Borel measurable function defined on the boundary and the (n–1)-dimensional Hausdorff measure on , we show that the semigroup generated by the Laplacian with Robin boundary conditions has always Gaussian estimates with modified exponents. We also obtain that the spectrum of the Laplacian with Robin boundary conditions in L ^p () is independent of p[1,). Our approach constitutes an alternative way to Daners who considers the (n–1)-dimensional Hausdorff measure on the boundary. In particular, it allows us to construct a conterexample disproving Daners' closability conjecture.     

Die Dupinschen Zykliden im pseudoeuklidischen Raum

In the pseudoeuclidean space¹ E ³ a surface of degree 3 or 4 is calledDupin-cyclide if there exists a (pseudoeuclidean) torus such that a (pseudoeuclidean) spherical inversion maps upon . If the axis of is respectively space-like, isotropic or time-like is calledDupin-r-,-l- or-z-cyclide. ADupin-cyclide is the envelope of two families of spheres, the caustic surfaces of degenerate in caustic curves and the lines of curvature of constitute two (orthogonal) families of circles.