On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Asymptotically independent topological indices on random trees

Topological indices are graph invariants used in computational chemistry to encode molecules. A frequent problem when performing structure-activity studies is that topological indices are inter-correlated. We consider a simple topological index and show asymptotic independence for a random tree model. This continues previous work on the correlation among topological indices. These findings suggest that a size-dependence in a certain class of distance-based topological indices can be eliminated.AMS subject classification: 05C80, 60E10, 92E10     

Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks

Summary Global relations between RNA sequences and secondary structures are understood as mappings from sequence space into shape space. These mappings are investigated by exhaustive folding of allGC andAU sequences with chain lengths up to 30. The computed structural data are evaluated through exhaustive enumeration and used as an exact reference for testing analytical results derived from mathematical models and sampling based on statistical methods. Several new concepts of RNA sequence to secondary structure mappings are investigated, among them that ofneutral networks (being sets of sequences folding into the same structure). Exhaustive enumeration allows to test several previously suggested relations: the number of (minimum free energy) secondary structures as a function of the chain length as well as the frequency distribution of structures at constant chain length (commonly resulting in generalized forms ofZipf's law).

---

Analyse der Beziehungen zwischen RNA-Sequenzen und Sekundärstrukturen durch vollständige Faltung, 1. Mitt. Faltung, Neutrale Netzwerke

Zusammenfassung Die globalen Benziehungen zwischen RNA-Sequenzen und Sekundärstrukturen werden als Abbildungen aus einem Raum aller Sequenzen in einen Raum aller Strukturen aufgefaßt. Diese Abbildungen werden durch Falten aller binären Sequenzen desGC-undAU-Alphabets mit Kettenlängen bis zun=30 untersucht. Die berechneten Strukturdaten werden durch vollständiges Abzählen ausgewertet und als eine exakte Referenz zum Überprüfen analytischer Resultate aus mathematischen Modellen sowie zum Testen statistisch erhobener Proben verwendet. Einige neuartige Konzepte zur Beschreibung der Beziehungen zwischen Sequenzen und Strukturen werden eingehend untersucht, unter ihnen der Begriff derneutralen Netzwerke. Ein neutrales Netzwerk besteht aus allen Sequenzen, die eine bestimmte Struktur ausbilden. Vollständiges Abzählen ermöglicht beispielsweise die Bestimmung aller Strukturen minimaler freier Energie in Abhängigkeit von der Kettenlänge ebenso wie die Bestimmung der Häufigkeitsverteilungen der Strukturen bei konstanten Kettenlängen. Die letzteren folgen einer verallgemeinerten FormZipfschen Gesetzes.

     

A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.     

Large cycles in random generalized Johnson graphs

This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for different growth rates.     

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.     

On input/output stabilization of singular integrodifferential systems

In this paper we consider a class of systems described by singular integrodifferential equations. This type of systems appear, for example, in the modeling of certain aeroelastic control problems. We study these systems in frequency domain framework and show the existence of finite-dimensional stabilizing controllers. An algorithmic procedure is outlined for the construction of such controllers. In order to illustrate the numerical aspects of this algorithm, we present an example involving the classical Theodorsen model of an airfoil, which fits in the class of systems considered here.This work was supported in part by the National Science Foundation under Grants DMS-8907019 and MSS-9203418.     

Near-perfect matrices

A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x0: Ax } can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.     

Disordered ground states for classical discrete-state problems in one dimension

It is known that one-dimensional lattice problems with a discrete, finite set of states per site generically have periodic ground states (GSs). We consider slightly less generic cases, in which the Hamiltonian is constrained by either spin (S) or spatial (I) inversion symmetry (or both). We show that such constraints give rise to the possibility ofdisordered GSs over a finite fraction of the coupling-parameter space—that is, without invoking any nongeneric fine tuning of coupling constants, beyond that arising from symmetry. We find that such disordered GSs can arise for many values of the number of statesk at each site and the ranger of the interaction. The Ising (k=2) case is the least prone to disorder:I symmetry allows for disordered GSs (without fine tuning) only forr5, whileS symmetry never gives rise to disordered GSs.