Circular Chromatic Number and Mycielski Graphs

As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graph G and denoted it by ^*(G). Later, Zhu called it circular chromatic number and denoted it by _c(G). Let (G) be the chromatic number of G. In this paper, it is shown that if the complement of G is non-hamiltonian, then _c(G)=(G). Denote by M(G) the Mycielski graph of G. Recursively define M^m(G)=M(M^m–1(G)). It was conjectured that if mn–2, then _c(M^m(K_n))=(M^m(K_n)). Suppose that G is a graph on n vertices. We prove that if , then _c(M(G))=(M(G)). Let S be the set of vertices of degree n–1 in G. It is proved that if |S| 3, then _c(M(G))=(M(G)), and if |S| 5, then _c(M²(G))=(M²(G)), which implies the known results of Chang, Huang, and Zhu that if n3, _c(M(K_n))=(M(K_n)), and if n5, then _c(M²(K_n))=(M²(K_n)).* Research supported by Grants from National Science Foundation of China and Chinese Academy of Sciences.     

The Colin de Verdière number and sphere representations of a graph

Colin de Vedière introduced an interesting linear algebraic invariant (G) of graphs. He proved that (G)2 if and only ifG is outerplanar, and (G)3 if and only ifG is planar. We prove that if the complement of a graphG onn nodes is outerplanar, then (G)n–4, and if it is planar, then (G)n–5. We give a full characterization of maximal planar graphs whose complementsG have (G)=n–5. In the opposite direction we show that ifG does not have twin nodes, then (G)n–3 implies that the complement ofG is outerplanar, and (G)n–4 implies that the complement ofG is planar.Our main tools are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks. In particular we show that such sphere representations characterize outerplanar and planar graphs.     

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 .)     

Mixing and some integro-functional equations

Summary It is proved that the operatorP: L ¹ (0, ) L ¹(0, ), given byPg(z) = _z/c [g(x)/cx]dx, is completely mixing, i.e.,P ⁿ g ₁ 0 forg L ¹(0, ) with g dx = 0. This implies that, forc (0, 1), each continuous and bounded solution of the equationf(x)= ₀ ^cx f(t)dt/(cx) (x (0, 1]) is constant.     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Differentiability properties of the minimal average action

Given aZ ⁿ⁺¹-periodic variational principle onR ⁿ⁺¹ we look for solutionsu:R ⁿ R minimizing the variational integral with respect to compactly supported variations. To every vector R ⁿ we consider a subset of solutions which have an average slope when averaging overR ⁿ. The minimal average action A() is defined by the average value of the variational integral given by a solution with average slope . Our main result is:A is differentiable at if and only if the set is totally ordered (in the natural sense). In case that is not totally ordered,A is differentiable at in some direction R ⁿ{0} if and only if is orthogonal to the subspace defined by the rational dependency of . Assuming that the i^th component of is rational with denominator sⁱ N in lowest terms, we show: The difference of right- and left-sided derivative in the i^th standard unit direction is bounded by const · .     

Sur la rigidité de certains groupes fondamentaux,l’arithméticité des réseaux hyperboliques complexes,et les “faux plans projectifs”

The motivation of this work comes from the study of lattices in real simple Lie groups. The famous Marguliss superrigidity theorem claims that finite dimensional reductive representations of any lattice of a real simple Lie group of real rank 2 are superrigid. As a corollary such a lattice is arithmetic. These results extend to the real rank one case for lattices in Sp(n,1) and F₄^(-20) by the work of Corlette and Gromov-Schoen. On the other hand Mostow and Deligne-Mostow exhibited arithmetic lattices with non-superrigid representations as well as non-arithmetic lattices in the unitary group PU(2,1). A natural question is then to find simple sufficient conditions for superrigidity or arithmeticity of lattices in PU(2,1). Rogawski conjectured the following: let be a torsion-free cocompact lattice in PU(2,1) such that the hyperbolic quotient M=\B² verifies the cohomogical conditions b₁(M)=0 and H^1,1(M,)H²(M,). Then is arithmetic. In this paper we consider a smooth complex projective surface M verifying the above cohomological assumptions and study Zariski-dense representations of the fundamental group ₁(M) in a simple k-group H of k-rank 2 (where k denotes a local field). Our main result states that there are strong restrictions on such representations, especially when k is non-archimedean (Theorem 5). We then consider some cocompact lattices in PU(2,1) of special geometric interest: recall that a fake P² is a smooth complex surface (distinct from P²) having the same Betti numbers as P². Fake P² exist by a result of Mumford and are complex hyperbolic quotients \H² by Yaus proof of the Calabi conjecture. They obviously verify the hypotheses of Rogawskis conjecture. In this case we prove that every Zariski-dense representation of in PGL(3) is superrigid in the sense of Margulis (Theorem 3). As a corollary every fake P² is an arithmetic quotient of the ball B².

---

     

On translations of double rays in graphs

Let be an infinite graph, let be a double ray in , and letd andd denote the distance functions in and in , respectively. One calls anaxis ifd(x,y)=d (x,y) and aquasi-axis if lim infd(x,y)/d (x,y)>0 asx, y range over the vertex set of andd (x,y). The present paper brings together in greater generality results of R. Halin concerning invariance of double rays under the action of translations (i.e., graph automorphisms all of whose vertex-orbits are infinite) and results of M. E. Watkins concerning existence of axes in locally finite graphs. It is shown that if is a translation whose directionD() is a thin end, then there exists an axis inD() andD(^–1) invariant under ^r for somer not exceeding the maximum number of disjoint rays inD().The thinness ofD() is necessary. Further results give necessary conditions and sufficient conditions for a translation to leave invariant a quasi-axis.     

Effective on-line coloring ofP 5-free graphs

An on-line algorithm is given that colors anyP ₅-free graph withf() colors, wheref is a function of the clique number of the graph.     

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 .     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

Clean triangulations

A polyhedron on a surface is called a clean triangulation if each face is a triangle and each triangle is a face. LetS _p (resp.N _p ) be the closed orientable (resp. nonorlentable) surface of genusp. If (S) is the smallest possible number of triangles in a clean triangulation ofS, the results are: (N ₁)=20, (S ₁)=24, lim(S _p )p ^–1=4, lim(N _p )p ^–1=2 forp.     

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.     

Packing random items of three colors

Consider three colors 1,2,3, and forj3, considern items (X _i,j)in of colorj. We want to pack these items inn bins of equal capacity (the bin size is not fixed, and is to be determined once all the objects are known), subject to the condition that each bin must contain exactly one item of each color, and that the total item sizes attributed to any given bin does not exceed the bin capacity. Consider the stochastic model where the random variables (X _i,jj)in,j3 are independent uniformly distributed over [0,1]. We show that there is a polynomial-time algorithm that produces a packing which has a wasted spaceK logn with overwhelming probability.Work partially supported by an N.S.F. grant.     

Eigenvalues of integral operators onL 2(I) given by analytic kernels

Let {_n} _n=0 be the eigenvalue sequence of a symmetric Hilbert-Schmidt operator onL ₂(I). WhenI is an open interval, a necessary condition for {_n} _n=0 to be in the sequence space is obtained. WhenI is a closed bounded interval, sufficient conditions for {_n} _n=0 to be in the sequence space ^– are obtained.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

On pseudo-differential operators and smoothness of special Lie-group representations

Two algebras of global pseudo-differential operators over ⁿ are investigated, with corresponding classes of symbols A⁰=CB (all (x, )-derivatives bounded over ²ⁿ), and A₁ (all finite applications of _xj, _j, and _pq=_pq–_px_p on the symbol are in A₀). The class A₁ consists of classical symbols, i.e., ^x a= 0((1+||)–^||) for x Kc ;ⁿ, K, compact. It is shown that a bounded operator A of 210C=L²(Rⁿ) is a pseudo-differential operator with symbol aA_j if and only if the map AG^–1AG, G g_j is infinitely differentiable, from a certain Lie-group g_j c GL(210C) to (210C) with operator norm. g₀ is the Weyl (or Heisenberg) group. Extensions to operators of arbitrary order are discussed. Applications to follow in a subsequent paper.Dedicated to Hans Lewy and Charles B. Morrey, Jr.     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

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.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.