Another family of chromatically unique graphs

LetP(G; ) denote the chromatic polynomial of a graphG, expressed in the variable. ThenG is said to be chromatically unique ifG is isomorphic withH for any graphH such thatP(H; ) = P(G; ). In this paper, we provide a new family of chromatically unique graphs.Research was partly supported by the University of Agriculture research grant # 50205-91-05     

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.     

Untere und obere Schranken für den tiefsten Eigenwert der elastisch gestützten Membran

Zusammenfassung Es werden untere und obere Schranken für den tiefsten Eigenwert ₁() der elastisch gestützten schwingenden Membran hergeleitet. Die elastische Bindung der Membran am Rande wird durch charakterisiert, und wird als Parameter betrachtet.Die Verwendung des klassischen Rayleigh-Prinzipes liefert obere Schranken, mit Hilfe eines konvexen FunktionalsJ() erhält man obere und untere Schranken. Eine Zerlegungsmethode endlich gibt eine untere Schranke für ₁().

---

Summary This article is concerned with the determination of upper and lower bounds for the lowest eigenvalue ₁() of the elastically supported vibrating membrane. The elastic support on the boundary is characterized by which is regarded as a parameter.The classical Rayleigh-Principle gives upper bounds. The use of a convex functionalJ() yields upper and lower bounds for ₁(). A method of decomposition leads to a lower bound for ₁().

---

---

Neu-Technikum, Buchs SG     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

A Result on Ext Over Kac–Moody Algebras

We prove the following result for a not necessarily symmetrizable Kac–Moody algebra: Let x,y W with x y, and let P⁺. If n=l(x)-l(y), then Ext _C() ⁿ (M(x·),L(y·))=1.     

A Proof of the Jungnickel-Tonchev Conjecture on Quasi-Multiple Quasi-Symmetric Designs

A proof of the following conjecture of Jungnickel and Tonchev on quasi-multiple quasi-symmetric designs is given: Let D be a design whose parameter set (v,b,r,k,) equals (v,sv,sk,k, s) for some positive integer s and for some integers v,k, that satisfy (v-1) = k(k-1) (that is, these integers satisfy the parametric feasibility conditions for a symmetric (v,k,)-design). Further assume that D is a quasi-symmetric design, that is D has at most two block intersection numbers. If (k, (s-1)) = 1, then the only way D can be constructed is by taking multiple copies of a symmetric (v,k, )-design.     

A sandwich theorem and Hyers—Ulam stability of affine functions

It is shown that two real functionsf andg, defined on a real intervalI, satisfy the inequalitiesf(x + (1 – )y) g(x) + (1 – )g(y) andg(x + (1 – )y) f(x) + (1 – )f(y) for allx, y I and [0, 1], iff there exists an affine functionh: I such thatf h g. As a consequence we obtain a stability result of Hyers—Ulam type for affine functions.     

Regularity of ∫Ω|∇u|2 + λ∫Ω|u−f{2 and some gap phenomenon

We study the regularity of the minimizer u for the functional F (u,f)=|u|² + |u–f{² over all maps uH ¹(, S ²). We prove that for some suitable functions f every minimizer u is smooth in if ₀ and for the same functions f, u has singularities when is large enough.

---

Résumé On étudie la régularité des minimiseurs u du problème de minimisation min_ueH ¹(,S²)(|u|² + |u–f{². On montre que pour certaines fonctions f, u est régulière lorsque ₀ et pour les mêmes f, si est assez grand, alors u possède des singularités.

     

Une méthode de comparaison isopérimétrique de fonctionnelles de domaines de la physique mathématique I. Première partie: une démonstration de la conjecture isopérimétrique Pλ2 ≥ πj 0 4 /2 de Pólya et Szegö

Résumé Soient _G la première valeur propre de la membrane à contour fixé sur un domaine simplement connexeG, etP _G la rigidité à la torsion deG. En construisant un cercleK tel queP _K P _G et _{K G}, on démontre la conjecture de Pólya et Szegö [14]; P_{G G} ² j ₀ ² /2. Ce résultat renforce le théorème isopérimétrique classique de Rayleigh [15], Faber [4] et Krahn [10].

---

Summary Let _G be the first eigenvalue of the fixed membrane on a simply connected domainG, and letP _G be the torsional rigidity ofG. We prove Pólya-Szegö's conjecture [14]: P_{G G} ² j ₀ ² /2, by constructing a circleK such thatP _K P _G and _{K G}. This result sharpens the classical isoperimetric theorem of Rayleigh [15], Faber [4] and Krahn [10].

     

Mixed graph colorings

A mixed graphG contains both undirected edges and directed arcs. Ak-coloring ofG is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallestk such thatG admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.     

Estimation of the Intensity of the Flow of Nonmonotone Refusals in the Queuing System (≤ λ)/G/m

We consider a queuing system ()/G/m, where the symbol () means that, independently of prehistory, the probability of arrival of a call during the time interval dtdoes not exceed dt. The case where the queue length first attains the level r m+ 1 during a busy period is called the refusal of the system. We determine a bound for the intensity ₁(t) of the flow of homogeneous events associated with the monotone refusals of the system, namely, ₁(t) = O( ^{r+ 1}₁ ^{m– 1} _{r– m+ 1}), where _k is the kth moment of the service-time distribution.     

Randomized graph products, chromatic numbers, and the Lovász ϑ-function

For a graphG, let (G) denote the size of the largest independent set inG, and let (G) denote the Lovász -function onG. We prove that for somec>0, there exists an infinite family of graphs such that \alpha (G)n/2^{c\sqrt {\log n} }$$ " align="middle" border="0"> , wheren denotes the number of vertices in a graph. this disproves a known conjecture regarding the function.As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.Incumbent of the Joseph and Celia Reskin Career Development Chair. Yigal Alon Fellow     

A technique for constructing divisible difference sets

An (m, n, k, ₁,₂) divisible difference set in a groupG of ordermn relative to a subgroupN of ordern is ak-subsetD ofG such that the list {xy^–1:x, y D} contains exactly ₁ copies of each nonidentity element ofN and exactly ₂ copies of each element ofG N. It is called semi-regular ifk > ₁ and k²=mn₂. We develop a method for constructing a divisible difference set as a product of a difference set and a relative difference set or a difference set and a subset ofG which we call a relative divisible difference set. The method results in several parametrically new families of semi-regular divisible difference sets.     

On the Movement of Transitive Permutation p-Groups

Let G be a transitive permutation group on a set and m a positive integer. If | – | m for every subset of and all g G, then || 2mp/(p – 1) where p is the least odd prime dividing |G|. It was shown by Mann and Praeger [13] that, for p = 3, the 3-groups G which attain this bound have exponent p. In this paper we will show a generalization of this result for any odd primes.AMS Subject Classification (2000), 20BXX     

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

The Spectral Theory of Amenable Actions and Invariants of Discrete Groups

Let G denote a semisimple group, a discrete subgroup, B=G/P the Poisson boundary. Regarding invariants of discrete subgroups we prove, in particular, the following:(1) For any -quasi-invariant measure on B, and any probablity measure on , the norm of the operator () on L ²(B,) is equal to (), where is the unitary representation in L ²(X,), and is the regular representation of .(2) In particular this estimate holds when is Lebesgue measure on B, a Patterson–Sullivan measure, or a -stationary measure, and implies explicit lower bounds for the displacement and Margulis number of (w.r.t. a finite generating set), the dimension of the conformal density, the -entropy of the measure, and Lyapunov exponents of .(3) In particular, when G=PSL₂() and is free, the new lower bound of the displacement is somewhat smaller than the Culler–Shalen bound (which requires an additional assumption) and is greater than the standard ball-packing bound.We also prove that ()=_G() for any amenable action of G and L ¹(G), and conversely, give a spectral criterion for amenability of an action of G under certain natural dynamical conditions. In addition, we establish a uniform lower bound for the -entropy of any measure quasi-invariant under the action of a group with property T, and use this fact to construct an interesting class of actions of such groups, related to 'virtual' maximal parabolic subgroups. Most of the results hold in fact in greater generality, and apply for instance when G is any semi-simple algebraic group, or when is any word-hyperbolic group, acting on their Poisson boundary, for example.     

A Note on Tortrat Groups

A locally compact group G is called a Tortrat group if for any probability measure on G which is not idempotent, the closure of {gg ^–1 | gG} does not contain any idempotent measure. We show that a connected Lie group G is a Tortrat group if and only if for all gG all eigenvalues of Ad g are of absolute value 1. Together with well-known results this also implies that a connected locally compact group is a Tortrat group if and only if it is of polynomial growth.     

Asymptotics for the wiener sausage with drift

Summary A particle is considered which moves in ^d according to a Brownian motion with drifth0. The space is assumed to contain random traps. The probability of survival of the particle up to timeT decays exponentially asT with a positive decay rate . is shown to be a non-analytic function of |h|. For small |h| the decay rate is given by (h)=1/2|h|²; but if |h| exceeds a certain critical value, (h) depends also on the parameters describing trapping. Upper and lower bounds for (h) are given, which imply the asymptotic linearity of (h) for large |h|. The critical point marks a transition from localized to delocalized behavior. A variational formula for the decay rate is given on the level of generalized processes, which elucidates the mathematical mechanism behind observations made earlier by Grassberger and Procaccia on the basis of computer simulations.Supported by Deutsche Forschungsgemeinschaft     

Algebraic systems of quadratic forms of number fields and function fields

In this paper we examine for which Witt classes ,..., _n over a number field or a function fieldF there exist a finite extensionL/F and ₂,..., _n L^* such thatT _L/F ()=1 andTr _L/F (_i)=_i fori=2,...n.     

Subdivision algorithms with nonnegative masks generally converge

In this paper, a subdivision scheme consists of an operator froml () tol () determined by a doubly infinite sequence, called the mask. This operator convolutes, in a certain sense, sequences l () with the mask, thus producing a new sequence inl (). Moreover, this new sequence is placed on a finer grid. If we iterate this process with a positive mask infinitely many times, it is known that this process will produce a continuous function, which we callf . In this paper, we consider the extent to which non-negative masks yield similar results. An important application of subdivision schemes in computer graphics is the generation of curves and surfaces from an initial sequence.