A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

Lines of curvature near umbilical points on surfaces immersed in R4

LetM be a compact orientable surface,I:M R⁴ an immersion of classC ^r and a normal unitary smooth vector field. We prove that in the space of pairs (I, ) the family of pairs all whose umbilical points are Darbouxian is generic.     

Large deviations for martingales with some applications

Let(X _i ) be a martingale difference sequence. LetY be a standard normal random variable. We investigate the rate of uniform convergence

Kneser-type oscillation criteria for self-adjoint two-term differential equations

It is proved that the even-order equationy ⁽²ⁿ⁾ +p(t)y=0 is (n,n) oscillatory at if

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.     

q-Sigma-algebra generated by balls

The q--algebra, i.e., the system of sets closed under complementation, countable disjoint unions, and containing the empty set, generated by the system of open balls coincides with the -field of Borel sets inR sun forn=1,2, and 3. A first step to extend the proof forn=4, 5, 6, and 7 is indicated.