Spectra of Large Random Trees

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity. Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees. We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree. For the linear preferential attachment model with parameter a>?1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by $n^{1/2\gamma_{a}}$ , where ?? _a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.     

Deterministic random walks on regular trees

Jim Propp's rotor–router model is a deterministic analog of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb Probab Comput 15 (2006) 815–822) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid ?^d and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips on this vertex deviates from the expected number the random walk would have gotten there by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite k‐ary tree (k ≥ 3), we show that for any deviation D there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least D more chips than expected in the random walk model. However, to achieve a deviation of D it is necessary that at least exp(Ω(D²)) vertices contribute by being occupied by a number of chips not divisible by k at a certain time. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Long range scattering for the modified Schrödinger map in two space dimensions

We study the asymptotic behaviour in time of solutions and the theory of scattering for the modified Schrödinger map in two space dimensions. We solve the Cauchy problem with large finite initial time, up to infinity in time, and we determine the asymptotic behaviour in time of the solutions thereby obtained. As a by product, we obtain global existence for small data in Hk∩FHk with k>1. We also solve the Cauchy problem with infinite initial time, namely we construct solutions defined in a neighborhood of infinity in time, with prescribed asymptotic behaviour of the previous type.     

Solving NP-hard problems in ‘almost trees’: Vertex cover

We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time $\text{O}\text{(|V|+(}\text{a}\text{k}\text{)2}{}^{\mathrm{<mtext>k</mtext><mtext>3</mtext>}}\text{)}$, where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches.     

Solving Non-Homogeneous Nested Recursions Using Trees

The solutions to certain nested recursions, such as Conolly’s C(n) = C(n?C(n?1)) + C(n?1?C(n?2)), with initial conditions C(1) = 1, C(2) = 2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, and its generalization to a similar k-term nested recursion, only apply to homogeneous recursions and only solve each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique also solves the given non-homogeneous recursion with various sets of initial conditions.     

Étale covers of affine spaces in positive characteristicRevêtements étales des espaces affines en caractéristique positive

We prove that every projective, geometrically reduced scheme of dimension n over an infinite field k of positive characteristic admits a finite morphism over some finite radicial extension k′ of k to projective n-space, étale away from the hyperplane H at infinity, which maps a chosen Weil divisor into H and a chosen smooth geometric point of X not on the divisor to some point not in H. To cite this article: K.S. Kedlaya, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 921–926.     

k-eccentricity and absolute k-centrum of a probabilistic tree

The k-eccentricity evaluated at a point x of a graph G is the sum of the (weighted) distances from x to the k vertices farthest from it. The k-centrum is the set of vertices for which the k-eccentricity is a minimum. The concept of k-centrum includes, as a particular case, that of center and that of centroid (or median) of a graph. The absolute k-centrum is the set of points (not necessarily vertices) for which the k-eccentricity is a minimum. In this paper it will be proven that, for a weighted tree, both deterministic and probabilistic, the k-eccentricity is a convex function and that the absolute k-centrum is a connected set and is contained in an elementary path. Hints will be given for the construction of an algorithm to find the k-centrum and the absolute k-centrum.     

An algebraic construction of the generic singularities of Boardman-Thom

In this paper we study some of the functorial properties of the infinite jet space in order to give a coordinate free algebraic definition of the generic singularities of Boardman-Thom. More precisely, suppose thatk is a commutative ring with an identity and suppose that A is a commutative ring with an identity which is ak-algebra. An A-k-Lie algebra L is ak-Lie algebra with ak-Lie algebra map ? from L to the algebra ofk-derivations of A to itself such that ford, d′εL anda, a′εA, then $$[ad'],a 'd'] = a(\varphi (d')ad' - a'(\varphi (d')a)d' + aa'[d',\;d'].$$ . There is a universal enveloping algebra for such Lie algebras which we denote by E(L). Denote byL-alg the category of A-algebras B which have L and hence E(L) acting as left operators such that foraεA,dεL, (da)i _B=d(a.i _B). If F is the forgetful functor fromL-alg to the category of A-algebras, we show that F has a left adjoint J(L, ·) which is the natural algebraic translation of the infinite jet space. In the third section of this paper we construct a theory of singularities for a derivation from a ring to a module and then we apply this construction to J(L, C) where C is an A-algebra. These singularities are subschemas with defining sheaf of ideals given by Fitting invariants of appropriately chosen modules when A and B are polynomial rings over a fieldk and C=A? _k B; these are the generic singularities of Boardman-Thom. Finally we show that, under some rather general conditions on the structure of C as an A-algebra, the generic singularities are regular immersions in the sense of Berthelot.     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

A new proof of the three squares theorem

A theorem of Fein, Gordon, and Smith on the representation of ?1 as a sum of two squares is shown to yield a new proof of the three squares theorem. A positive integer k can be represented as a sum of three integer squares if and only if k ≠ 4^an with n ≡ 7 (mod 8) and a ≥ 0. This proof depends of the Brauer group and class field theory, not on ternary quadratic forms.     

Outlets of 2D invasion percolation and multiple-armed incipient infinite clusters

We study invasion percolation in two dimensions, focusing on properties of the outlets of the invasion and their relation to critical percolation and to incipient infinite clusters (IICs). First we compute the exact decay rate of the distribution of both the weight of the kth outlet and the volume of the kth pond. Next we prove bounds for all moments of the distribution of the number of outlets in an annulus. This result leads to almost sure bounds for the number of outlets in a box B(2 ⁿ ) and for the decay rate of the weight of the kth outlet to p _c . We then prove existence of multiple-armed IIC measures for any number of arms and for any color sequence which is alternating or monochromatic. We use these measures to study the invaded region near outlets and near edges in the invasion backbone far from the origin.     

On monotone functions of tree structures

Let T be a rooted tree structure with n nodes a₁,…,a_n. A function f: {a₁,…,a_n} into {1 < ? < k} is called monotone if whenever a_i is a son of a_j, then f(a_i) ≥ f(a_j). The average number of monotone bijections is determined for several classes of tree structures. If k is fixed, for the average number of monotone functions asymptotic equivalents of the form c · ?^?nn^{?$\text{3}\text{2}$} (n → ∞) are obtained for several classes of tree structures.     

Asymptotic of the Critical Value of the Large-Dimensional SIR Epidemic on Clusters

In this paper we are concerned with the susceptible-infective-removed (SIR) epidemic on open clusters of bond percolation on the square lattice. For the SIR model, a susceptible vertex is infected at rate proportional to the number of infective neighbors, while an infective vertex becomes removed at a constant rate. A removed vertex will never be infected again. We assume that at \(t=0\) the only infective vertex is the origin and define the critical value of the model as the supremum of the infection rates with which infective vertices die out with probability one; then, we show that the critical value under the annealed measure is \(\big (1+o(1)\big )/(2dp)\) as the dimension d of the lattice grows to infinity, where p is the probability that a given edge is open. Furthermore, we show that the critical value under the quenched measure equals the annealed one when the origin belongs to an infinite open cluster of the percolation.     

Nested cycles in large triangulations and crossing-critical graphs

We show that every sufficiently large plane triangulation has a large collection of nested cycles that either are pairwise disjoint, or pairwise intersect in exactly one vertex, or pairwise intersect in exactly two vertices. We apply this result to show that for each fixed positive integer k, there are only finitely many k-crossing-critical simple graphs of average degree at least six. Combined with the recent constructions of crossing-critical graphs given by Bokal, this settles the question of for which numbers q>0 there is an infinite family of k-crossing-critical simple graphs of average degree q.     

One-way multiparty communication lower bound for pointer jumping with applications

In this paper we study the one-way multiparty communication model, in which every party speaks exactly once in its turn. For every k, we prove a tight lower bound of Ω(n ^1/(k?1)}) on the probabilistic communication complexity of pointer jumping in a k-layered tree, where the pointers of the i-th layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (logn)^1/2?? parties, for any constant ? > 0. Previous to our work a lower bound was known only for k =3 (Wigderson, see [7]), and in restricted models for k>3 [2},24,18,4,13]. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture general (not one-way) multiparty protocols with a bounded number of rounds. Thus we generalize two problem areas previously studied in the 2-party model (cf. [30,21,29]). The first is a rounds hierarchy: we give an exponential separation between the power of r and 2r rounds in general probabilistic k-party protocols, for any k and r. The second is the relative power of determinism and nondeterminism: we prove an exponential separation between nondeterministic and deterministic communication complexity for general k-party protocols with r rounds, for any k,r. The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Ω(n ^1/(k?1)) on the probabilistic complexity of k-set disjointness in the one-way model, which was known only for k = 3 parties. Our result also extends a similar lower bound for the weaker simultaneous model, in which parties simultaneously send one message to a referee [12]. Finally, we infer an exponential separation between the power of any two different orders in which parties send messages in the one-way model, for every k. Previous results [29, 7] separated orders based on who speaks first. Our lower bound technique, which handles functions of high discrepancy over cylinder intersections, provides a “party-elimination” induction, based on a restricted form of a direct-product result, specific to the pointer jumping function.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Log-convexity and log-concavity of hypergeometric-like functions

We find sufficient conditions for log-convexity and log-concavity for the functions of the forms a?∑fkk(a)xk, a?∑fkΓ(a+k)xk and a?∑fkxk/k(a). The most useful examples of such functions are generalized hypergeometric functions. In particular, we generalize the Turán inequality for the confluent hypergeometric function recently proved by Barnard, Gordy and Richards and log-convexity results for the same function recently proved by Baricz. Besides, we establish a reverse inequality which complements naturally the inequality of Barnard, Gordy and Richards. Similar results are established for the Gauss and the generalized hypergeometric functions. A conjecture about monotonicity of a quotient of products of confluent hypergeometric functions is made.     

Multiple solutions for a class of elliptic equations with jumping nonlinearities

We consider a semilinear elliptic Dirichlet problem with jumping nonlinearity and, using variational methods, we show that the number of solutions tends to infinity as the number of jumped eigenvalues tends to infinity. In order to prove this fact, for every positive integer k we prove that, when a parameter is large enough, there exists a solution which presents k interior peaks. We also describe the asymptotic behaviour and the profile of this solution as the parameter tends to infinity.