On a topological characterization of the real line

M.C. Zdun [17] asked whether a subset S of R² such that R × S is homeomorphic to R² must be homeomorphic to R, all these sets being endowed with the usual topologies. We show that the answer is affirmative.     

Computing global minima to polynomial optimization problems using Gröbner bases

The local optimality conditions to polynomial optimization problems are a set of polynomial equations (plus some inequality conditions). With the recent techniques of Gröbner bases one can find all solutions to such systems, and hence also find global optima. We give a short survey of these methods. We also apply them to a set of problems termed with exact solutions unknown in the problem sets of Hock and Schittkowski. To these problems we give exact solutions.     

On the capacity of boolean graph formulæ

In a recent paper we have solved several well-known combinatorial problems treating them as special cases of our generalization of Shannon's notion of graph capacity. We present a new simple formalism to deal with all such problems in a unified manner, considering graphs or families of graphs as special formulæ the variables of which are pairs of vertices of their common vertex sets. In all of these problems, the maximum size of a set ofn-length sequences from a fixed alphabet is to be determined under various restrictions on the element pairs present in the same coordinate of any two sequences from the set. For sufficiently homogeneous formulæ capacity becomes computable.New applications include generalizations of our result on the maximum number of pairwise qualitatively independentk-partitions of ann-set from independence to various forms of qualitative dependence.Work partially supported by the Italian Ministry of the University and Scientific Research, Project: Algoritmi, Modelli di Calcolo e Strutture Informative.     

Spectra of graphs and fractal dimensions II

This paper continues the study of exponentsd(x), d (x), d _R (x) andd (x) for graphG; and the nearest neighbor random walk {X _n } _nN onG, if the starting pointX ₀=x is fixed. These exponents are responsible for the geometric, resistance, diffusion and spectral properties of the graph. The main concern of this paper is the relation of these exponents to the spectral density of the transition matrix. A series of new exponentse, e ,e _R ,e are introduced by allowingx to vary along the vertices. The results suggest that the geometric and resistance properties of the graph are responsible for the diffusion speed on the graph.     

Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.