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.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.     

An upper bound for the total chromatic number

The total chromatic number,(G), of a graphG, is defined to be the minimum number of colours needed to colour the vertices and edges of a graph in such a way that no adjacent vertices, no adjacent edges and no incident vertex and edge are given the same colour. This paper shows that , where(G) is the vertex chromatic number and(G) is the edge chromatic number of the graph.Partially supported by ORS grant ORS/84120     

The Topology of the Coloring Complex

In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex _G, referred to as the coloring complex of G. Certain nonfaces of _G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial _G of G, and the reduced Euler characteristic is, up to sign, equal to |_G(–1)|–1. We show that _G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of _G, and their Euler characteristics coincide with _G(0) and –_G(1), respectively. We show for a large class of graphs—including all connected graphs—that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Research financed by ECs IHRP Programme, within the Research Training Network Algebraic Combinatorics in Europe, grant HPRN-CT-2001-00272.     

Subcoercivity and subelliptic operators on Lie groups II: The general case

Let (,G, U) be a continuous representation of a Lie groupG by bounded operatorsg U (g) on the Banach space and let (, ,dU) denote the representation of the Lie algebra obtained by differentiation. Ifa ₁, ...,a _d is a Lie algebra basis of ,A _i =dU (a _i ) and whenever =(i ₁, ...,i _k ) we reconsider the operators

Irreducible representations of Lie algebras of reductive groups and the Kac-Weisfeiler conjecture

Letg be the Lie algebra of a connected reductive groupG over an algebraically closed field of characteristicp>0. Suppose thatG ⁽¹⁾ is simply connected andp is good for the root system ofG. Ifp=2, suppose in addition thatg admits a nondegenerateG-invariant trace form. LetV be an irreducible and faithfulg-module withp-character g ^*. It is proved in the paper that dimV is divisible byp ^1/2dim() where () stands for the orbit of under the coadjoint action ofG.Oblatum 14-III-1994 & 17-XI-1994     

Star chromatic numbers of graphs

We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou.     

Some Non-trivial Symmetry Classes of Tensors Associated with Certain Characters

Let G be a finite group and a set of n elements. Assume that G acts faithfully on and let V be a vector space over the complex field , with dim V = m 2. It is shown that for each irreducible constituent of permutation character of G, the symmetry class of tensors associated with G and is non-trivial. This extends a result of Merris and Rashid (see [6, Theorem 2]).1995 AMS subject classification primary 20C30 secondary 15A69This research was in part supported by a grant from IPM.     

A variational principle for eigenvalues of pencils of Hermitian matrices

LetH=(A, B) be a pair of HermitianN×N matrices. A complex number is an eigenvalue ofH ifdet(A–B)=0 (we include = ifdetB=0). For nonsingularH (i.e., for which some is not an eigenvalue), we show precisely which eigenvalues can be characterized as _k ⁺ =sup{inf{*A:*B=1,S},SS _k},S _k being the set of subspaces of C ^N of codimensionk–1.Dedicated to the memory of our friend and colleague Branko NajmanResearch supported by NSERC of Canada and the I.W.Killam FoundationProfessor Najman died suddenly while this work was at its final stage. His research was supported by the Ministry of Science of CroatiaResearch supported by NSERC of Canada     

On the Coates–Sinnott Conjecture

Let E signify a totally real Abelian number field with a prime power conductor and ring of pintegers R _E for a prime p. Let G denote the Galois group of E over the rationals, and let be a padic character of G of order prime to p. Theorem A calculates, under a minor restriction on , the Fitting ideals of H ² _ét(R _E;Z _p (n/2+1))() over Z _p [G](). Here we require that n2 mod 4. These Fitting ideals are principal and generated by a Stickelberger element. This gives a partial verification and also a strong indication of the Coates–Sinnott conjecture.     

Dense graphs and edge reconstruction

By a well-known result of Nash-Williams if a graphG is not edge reconstructible, then for all ,|A||E(G)| mod 2 we have a permutation ofV(G) such thatE(G)E(G)=A. Here we construct infinitely many graphsG having this curious property and more than edges.Research (partially) supported by Hungarian National Foundation for Scientific Research Grant No.T016389.     

The search for chromatically unique graphs

The number of vertex-colourings of a simple graphG in not more than colours is a polynomial in. This polynomial, denoted byP(G, ), is called the chromatic polynomial ofG. A graphG is said to be chromatically unique, in short-unique, ifH G for any graphH withP(H, ) = P(G, ). Since the appearance of the first paper on-unique graphs by Chao and Whitehead in 1978, various families of and several results on such graphs have been obtained successively, especially during the last five years. It is the aim of this expository paper to give a survey on most of the works done on-unique graphs. A number of related problems and conjectures are also included.1980 Mathematical Subject Classification. Primary 05C15This work was done while the author was visiting the Department of Mathematics, National University of Singapore.     

Critical star multigraphs

A star-multigraphG is a multigraph in which there is a vertexv ⁺ which is incident with each non-simple edge. It is critical if it is connected, Class 2 and(G\e) < (G) for eache E(G). We show that, ifG is any star multigraph, then(G) (G) + 1. We investigate the edge-chromatic class of star multigraphs with at most two vertices of maximum degree. We also obtain a number of results on critical star multigraphs. We shall make use of these results in later papers.     

Approximation in the mean by bounded analytic functions

Let 1<p< and . LetC _q denote the Bessel capacity in the plane. Let be the set of homomorphisms ofH (G) such that (z)= and letNP denote the set of points in G for which is not a peak set forH (G). In this note, we show that ifC _q (NP)=0, thenH (G) is dense inL _a ^p (G), the Bergman space overG.Partially supported by NSF DMS-9401234     

The non-cancellation group of a direct power of a (finite cyclic)-by-cyclic group

If M is a finitely generated group having a finite commutator subgroup, then the set (M) of all isomorphism classes of groups G such that G×M× is a finite set and coincides with the Mislin genus (M) of M if M is nilpotent. For such groups M, there is a group structure on (M) defined in terms of the indices of embeddings of G into M, for groups G representing elements of (M). Such embeddings do exist and their indices are necessarily finite. If M is nilpotent, then this group structure on (M) coincides with the Hilton-Mislin group structure on the genus of M. In this paper we calculate the group (H^k) where H^k is the direct product of k copies of a group the form H= a,b | aⁿ=1, bab^-1=a^u, for any relatively prime pair of natural numbers n,u. In particular we find that for each such group H we have an isomorphism (H²)(H^k) whenever k>2.The author wishes to acknowledge financial support from the National Research Foundation of South Africa.Mathematics Subject Classification (2000): 20E34, 20F28Revised version: 10 December 2003     

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.     

Wave operators in a multistratified strip

One investigates the scattering theory for the positive self-adjoint operatorH=–· acting in with = × and a bounded open set in ^n–1,n2. The real-valued function belongs toL (), is bounded from below byc>0 and there exist real-valued functions ₁ and ₂ inL () such that – _j ,j=1,2 is a short range perturbation of _j when (–1) ^j x _n +. One assumes _j = ^(j) 1_R,j=1,2, with ^(j) L bounded from below byc>0. One proves the existence and completeness of the generalized wave operators _j ^± =s – _j e ^–itHj ,j=1,2, withH _j =–· _j and _j : equal to 1 if (–1) ^j x _n >0 and to 0 if (–1) ^j x _n <0. The ranges ofW _j ^± :=( _j ^± )^* are characterized so that W ₁ ^± =Ran and . The scattering operator can then be defined.     

Designs and partial geometries over finite fields

Let be a finite field, and let (, B) be a nontrivial 2-(n, k, 1)-design over . Then each point induces a (k–1)-spread S on /. (, B) is said to be a geometric design if S is a geometric spread on / for each . In this paper, we prove that there are no geometric designs over any finite field .Research partially supported by NSF grant DMS-8703229.     

An application of Shoenfield's absoluteness theorem to the theory of uniform distribution

IfC is a Polish probability space, a Borel set whose sectionsW _x ( have measure one and are decreasing , then we show that the set _x W _x has measure one. We give two proofs of this theorem—one in the language of set theory, the other in the language of probability theory, and we apply the theorem to a question on completely uniformly distributed sequences.Supported by DFG grant Ko 490/7-1.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.