Local Tree-Width,Excluded Minors,and Approximation Algorithms

The local tree-width of a graph G=(V,E) is the function ltw^G : that associates with every r the maximal tree-width of an r-neighborhood in G. Our main grapht heoretic result is a decomposition theorem for graphs with excluded minors, which says that such graphs can be decomposed into trees of graphs of almost bounded local tree-width.As an application of this theorem, we show that a number of combinatorial optimization problems, suchas Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.     

Additive Completion of Lacunary Sequences

To the memory of Pál Erdős Thirty years ago I read the following question of Erdőos [4]: "Does there exist a sequence with so that every sufficiently large number is of the form ? $10" I sent my solution to Erdős in a letter (in Hungarian). He translated my letter into English and sent it to the Canadian Math. Bulletin; this became my first paper to appear. In this paper we will find, among others, the best value of the constant c in the above question, which was also asked by Erdős. Received March 30, 2000 RID="*" ID="*" Supported by Hungarian National Foundation for Scientific Research, Grants No. T 025617 and T 29759.     

On the spherical symmetry of static perfect fluids in general relativity

We present a theorem which establishes uniqueness, in particular spherical symmetry, of a wide class of general relativistic, static perfect-fluid models provided there exists a spherically symmetric model with the same equation of state and surface potential. The method of proof, which is inspired by recent work of Masood-ul-Alam, is illustrated by demonstrating uniqueness of a class of solutions due to Buchdahl which correspond to an extreme case of the inequality on the equation of state required by our theorem.     

Fermions in a two-dimensional theory of gravity with dynamical metric and torsion

We propose a new model which reduces a two-dimensional gravitational model with dynamical metric and torsion in a conformal gauge. We also find the instanton-like solutions and discuss their symmetry properties and eigenmodes.This work was partially supported by TBTAK, the Scientific and Technical Research Council of Turkey.     

On finsler spaces satisfying theT-condition

A Finsler space has been shown to satisfy theT-condition if the Finslerian metric tensor is quadratic in the unit tangent vectors. In the case where the curvature tensor of the indicatrix vanishes the converse statement is valid. The wide class of the Finslerian metric functions satisfying the condition of the quadratic dependence of the metric tensor on the unit tangent vectors, and hence theT-condition, has been found.     

Mathematical problems of stochastic quantum mechanics: Harmonic analysis on phase space and quantum geometry

In this paper we review the mathematical methods and problems that are specific to the programme of stochastic quantum mechanics and quantum spacetime. The physical origin of these problems is explained, and then the mathematical models are developed. Three notions emerge as central to the programme: positive operator-valued (POV) measures on a Hilbert space, reproducing kernel Hilbert spaces, and fibre bundle formulations of quantum geometries. A close connection between the first two notions is shown to exist, which provides a natural setting for introducing a fibration on the associated overcomplete family of vectors. The introduction of group covariance leads to an extended version of harmonic analysis on phase space. It also yields a theory of induced group representations, which extends the results of Mackey on imprimitivity systems for locally compact groups to the more general case of systems of covariance. Quantum geometries emerge as fibre bundles whose base spaces are manifolds of mean stochastic locations for quantum test particles (i.e., spacetime excitons) that display a phase space structure, and whose fibres and structure groups contain, respectively, the aforementioned overcomplete families of vectors and unitary group representations of phase space systems of covariance.Work supported in part by the Natural Science and Engineering Research Council of Canada (NSERC) grants.     

Harmonic analysis and systems of covariance for phase space representation of the poincaré group

Continuing some earlier work on the Galilei group, the spectral resolution of phase space representations of the Poincaré group is achieved by deriving all possible decompositions into irreducible representations corresponding to reproducing, kernel Hilbert spaces. Systems of covariance related to quantum measurements performed with extended test particles are analyzed, and questions of global unitarity discussed.Supported in part by NSERC Research Grants.     

Complete Minors In <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">s,s</Emphasis></Subscript>-Free Graphs

We prove that for a fixed integer s2 every K _s,s -free graph of average degree at least r contains a K _p minor where . A well-known conjecture on the existence of dense K _s,s -free graphs would imply that the value of the exponent is best possible. Our result implies Hadwigers conjecture for K _s,s -free graphs whose chromatic number is sufficiently large compared with s.     

Any 7-Chromatic Graphs Has K 7 Or K 4,4 As A Minor

In 1943, Hadwiger made the conjecture that every k-chromatic graph has a K _k -minor. This conjecture is, perhaps, the most interesting conjecture of all graph theory. It is well known that the case k=5 is equivalent to the Four Colour Theorem, as proved by Wagner [39] in 1937. About 60 years later, Robertson, Seymour and Thomas [29] proved that the case k=6 is also equivalent to the Four Colour Theorem. So far, the cases k7 are still open and we have little hope to verify even the case k=7 up to now. In fact, there are only a few theorems concerning 7-chromatic graphs, e. g. [17].In this paper, we prove the deep result stated in the title, without using the Four Colour Theorem [1,2,28]. This result verifies the first unsettled case m=6 of the (m,1)-Minor Conjecture which is a weaker form of Hadwigers Conjecture and a special case of a more general conjecture of Chartrand et al. [8] in 1971 and Woodall [42] in 1990.The proof is somewhat long and uses earlier deep results and methods of Jørgensen [20], Mader [23], and Robertson, Seymour and Thomas [29].* Research partly supported by the Japan Society for the Promotion of Science for Young Scientists. Research partly supported by the Danish Natural Science Research Council.Dedicated to Professor Mike Plummer on the occasion of his sixty-fifth birthday.     

Integer parts of powers of rational numbers

We prove that the sequence [ξ(5/4)ⁿ], n=1,2, . . . , where ξ is an arbitrary positive number, contains infinitely many composite numbers. A corresponding result for the sequences [(3/2)ⁿ] and [(4/3)ⁿ],n=1,2, . . . , was obtained by Forman and Shapiro in 1967. Furthermore, it is shown that there are infinitely many positive integers n such that ([ξ(5/4)ⁿ],6006)>1, where 6006=2·3·7·11·13. Similar results are obtained for shifted powers of some other rational numbers. In particular, the same is proved for the sets of integers nearest to ξ(5/3)ⁿ and to ξ(7/5)ⁿ, n∈ℕ. The corresponding sets of possible divisors are also described.