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.     

The existence of minimal large positive solutions for a class of nonlinear cooperative systems

In this paper we establish the existence of the minimal large positive solution for a general class of nonlinear cooperative systems including the simplest prototype of García-Melián et al. (2016). Precisely, based on the existence of a large positive supersolution, we can infer the existence of the minimal large positive solution. Moreover, we also give some sufficient easily computable conditions for the existence of a large positive supersolution. Our results generalize, very substantially, some of the findings of García-Melián et al. (2016) adopting a rather novel methodology.     

Maximum principle at infinity for complete minimal surfaces in flat 3-manifolds

The main result of this paper is the following maximum principle at infinity:Theorem.Let M ₁ and M ₂ be two disjoint properly embedded complete minimal surfaces with nonempty boundaries, that are stable in a complete flat 3-manifold. Then dist(M ₁,M ₂)=min(dist(M ₁,M ₂), dist(M ₂,M ₁)).In case one boundary is empty, e.g. M ₁,then dist(M ₁,M ₂)=dist(M ₂,M ₁).If both boundaries are empty, then M ₁ and M ₂ are flat.     

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.     

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.     

Sur les metriques admettant les plans comme surfaces minimales

We establish the system of partial differential equations satisfied by the riemannian metrics on open subsets of which admit planes as minimal surfaces. This is a nonlinear system of 10 partial differential equations, with the euclidian metric as a particular solution. In a previous work, we solved this system for axially symmetrical metrics. In this paper we linearize the system at the euclidian metric and solve the linear system. We obtain a 20-dimensional space of solutions.

     

Rigorous results on the thermodynamics of the dilute Hopfield model

We study the Hopfield model of an autoassociative memory on a random graph onN vertices where the probability of two vertices being joined by a link isp(N). Assuming thatp(N) goes to zero more slowly thanO(1/N), we prove the following results: (1) If the number of stored patternsm(N) is small enough such thatm(N)/Np(N) 0, asN, then the free energy of this model converges, upon proper rescaling, to that of the standard Curie-Weiss model, for almost all choices of the random graph and the random patterns. (2) If in additionm(N) < ln N/ln 2, we prove that there exists, forT< 1, a Gibbs measure associated to each original pattern, whereas for higher temperatures the Gibbs measure is unique. The basic technical result in the proofs is a uniform bound on the difference between the Hamiltonian on a random graph and its mean value.