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.     

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.

     

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 minimax principle for the critical value of a boundary value problem with positive and increasing nonlinearity

Summary For a non-linear boundary value problem with a positive and increasing non-linearity there exists a critical value* of the parameter, beyond which there are no solutions. We give a minimax characterization of*.

---

Zusammenfassung In der Randwertaufgabe –u(x)=f(x, u(x)), u(a)=u(b)=0, seif positiv und wachsend im zweiten Argument. Dann gibt es einen Wert*, so dass keine Lösung existiert für>*. In dieser Arbeit wird* durch ein Minimaxprinzip charakterisiert. Der Beweis beruht auf der Anwendung von Ober- und Unterlösungen und monotonen Iterationen.

     

On polynomial EkP matrices

In this paper the relation betweenEP--matrices andE ^k P--matrices over an arbitrary filedF is studied. Further, conditions for the product ofE ^k P--matrices to be anE ^k P--matrix and for the reverse order law to hold for the polynomial Moore-Penrose inverse of the product ofE ^k P--matrices are determined     

Continuous Singularity of the Weak Limit of Convolution Powers of a Discrete Probability Measure on 2 × 2 Stochastic Matrices

Let be a probability measure on n 2 × 2 stochastic matrices, n an arbitrary positive integer, and = (w) lim _n ⁿ , such that the support of consists of 2 × 2 stochastic matrices of rank one, and as such, can be regarded as a probability measure on [0, 1]. We present simple sufficient conditions for to be continuous singular w.r.t. the Lebesgue measure on [0, 1]. We also determine , given .     

On the number of non conjugate subgroups

We shall prove that every group of cardinality ₁ has at least ₁ non conjugate subgroups, and we shall generalize this theorem to many more uncountable cardinalities. For example underGCH for every uncountable cardinal and every groupG of cardinality ,G has at least non conjugate subgroups.Presented by W. Taylor.I would like to thank Rami Grossberg for writing and rewriting this paper, and Wilfrid Hodges for removing many errors and suggesting improvements in presentation; many facts are proved only due to his explicit request.This research was supported by grant (No. 1110) from the United States-Israel Binational Science Foundation.     

Spectral parameter asymptotics of the Weyl solutions of Sturm-Liouville equations

In the paper one investigates the dependence of Weyl's solution ,)=c(,)+n()s(,) of the Sturm-Liouville equation y+q()y=²y on the spectral parameter . Under the condition that the potential q is bounded from below and q()exp(c₀+c[in1 ¦¦), it is proved for {ie217-01} for any positive values and A. If q()>1 and {ie217-02} for all >0, then in the semiplane >0 the Weyl solution (, ) is obtained from the Weyl solution (,x) is obtained from the Weyl solution e^ix with zero potential, with the aid of a generalization of B. Ya Levin's transformation operators.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 170, pp. 184–206, 1989.I express my sincere gratitude to L. A. Pastur and I. V. Ostrovskii for valuable advice and discussions.     

Cones of highest weight vectors, weight polytopes, and Lusztig's q-analog

We relate the invariant theory of cones of highest weight vectors to weight multiplicities and theirq-analogs. Whenever the action of a maximal torus on the coneC^* has some nice properties, we obtain simple closed formulas for all weight multiplicities and theirq-analogs in the representationsV _n ,n. We find a connection between the character ofV _n and the respective weight polytopes.This research was supported in part by the Alexander von Humboldt Foundation and INTAS Grant No. 93-0893     

Nonnegative Hall Polynomials

The number of subgroups of type and cotype in a finite abelian p-group of type is a polynomialg with integral coefficients. We prove g has nonnegative coefficients for all partitions and if and only if no two parts of differ by more than one. Necessity follows from a few simple facts about Hall-Littlewood symmetric functions; sufficiency relies on properties of certain order-preserving surjections that associate to each subgroup a vector dominated componentwise by . The nonzero components of (H) are the parts of , the type of H; if no two parts of differ by more than one, the nonzero components of – (H) are the parts of , the cotype of H. In fact, we provide an order-theoretic characterization of those isomorphism types of finite abelian p-groups all of whose Hall polynomials have nonnegative coefficients.     

Canonical and Boundary Representations on the Lobachevsky Plane

Canonical representations on Hermitian symmetric spaces G/K were introduced by Vershik, Gelfand and Graev and Berezin. They are unitary. We study canonical representations in a wider sense. In this paper we restrict ourselves to a crucial example – the Lobachevsky plane: G=SU(1,1), K=U(1). Canonical representations are labelled by the complex parameter (Vershik–Gelfand–Graev's representations correspond to –3/2<<0). We decompose the canonical representations into irreducible components. The decomposition includes boundary representations generated by the canonical representations. So we study these boundary representations themselves. The decomposition of boundary representations is closely connected with the meromorphic structure of Poisson and Fourier transforms associated with canonical representations. In particular, second-order poles give second-order Jordan blocks. Finally, we give a full decomposition of the Berezin transform using generalized powers (Pochhammer symbols) instead of usual powers of .     

Bounds of eigenvalues of a graph

LetG be a simple graph withn vertices. We denote by _i(G) thei-th largest eigenvalue ofG. In this paper, several results are presented concerning bounds on the eigenvalues ofG. In particular, it is shown that –1₂(G)(n–2)/2, and the left hand equality holds if and only ifG is a complete graph with at least two vertices; the right hand equality holds if and only ifn is even andG2K _n/2.     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

On a problem of A. Pleijel

In 1955, Arne Pleijel proposed the following problem which remains unsolved to this day: Given a closed plane convex curve C and a point x() at a fixed distance above the plane, as the point x() varies, characterize the point for which the conical surface with vertex x() and base C attains its minimum, and determine the limits as 0 and of this minimum point. The purpose of this paper is to solve the cases where approach its extremities and in the course of the solution, we obtain an interesting characterization of the limit points, which we shall call the Pleijel points of C. A consequence is that the inner Pleijel point provides an upper bound for the isoperimetric defect of C. We also generalize the problem to higher dimensional spaces, and obtain the corresponding characterizations of the limiting points for convex surfaces.     

The dynamics of perturbations of the contracting Lorenz attractor

We show here that by modifying the eigenvalues ₂ < ₃ < 0 < ₁ of the geometric Lorenz attractor, replacing the usualexpanding condition ₃+₁ > 0 by acontracting condition ₃+₁ < 0, we can obtain vector fields exhibiting transitive non-hyperbolic attractors which are persistent in the following measure theoretical sense: They correspond to a positive Lebesgue measure set in a twoparameter space. Actually, there is a codimension-two submanifold in the space of all vector fields, whose elements are full density points for the set of vector fields that exhibit a contracting Lorenz-like attractor in generic two parameter families through them. On the other hand, for an open and dense set of perturbations, the attractor breaks into one or at most two attracting periodic orbits, the singularity, a hyperbolic set and a set of wandering orbits linking these objects.     

Asymptotic behavior of the spectrum of the Maxwell operator

For the distribution functions of the positive and the negative eigenvalues of the operator in a domain with a smooth boundary, one obtains the asymptotic formula N^±()=(3²)^–1 mes ·³+0(²). Under additional assumptions on the properties of the geodesic billiard in , one shows that N±()= (3²)^–1 mes ·³+0(²).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 127, pp. 169–180, 1983.     

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

     

Steepest Descent with Curvature Dynamical System

Let H be a real Hilbert space and let <..,.> denote the corresponding scalar product. Given a function that is bounded from below, we consider the following dynamical system:

On the immersion of metrics close to immersible metrics

For a C^r,-immersion z:X E, r 2, 0 < < 1, of an n-dimensional (n 1) simply-connected C^r+2,-manifold X into Euclidean space E, the metric I(z) induced by z has a neighborhood in C^r,-topology in which every metric from a given subbundle of metrics is C^r,-immersible into E. In particular, it is proved that metric ds ₀ ² of the Riemannian product of p spheres of dimensions ₁, , _p 2 has a neighborhood in C^2,-topology from which any conformally equivalent metric to ds ₀ ² , is immersible into E with dimE = ₁ + + _p + p. The proofs are based on the investigation of a varied system of Gauss—Codazzi—Ricci equations for an infinitely small deformation of surface z(X) in E with a prescribed variation of the metric.Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 49–67, 1992.