The intermediate disorder regime for a directed polymer model on a hierarchical lattice

We study a directed polymer model defined on a hierarchical diamond lattice, where the lattice is constructed recursively through a recipe depending on a branching number $b\in \mathbb{N}$ and a segment number $s\in \mathbb{N}$. When $b\le s$ it is known that the model exhibits strong disorder for all positive values of the inverse temperature $\beta$, and thus weak disorder reigns only for $\beta =0$ (infinite temperature). Our focus is on the so-called intermediate disorder regime in which the inverse temperature $\beta \equiv {\beta }_n$ vanishes at an appropriate rate as the size $n$ of the system grows. Our analysis requires separate treatment for the cases $b<s$ and $b=s$. In the case $b<s$ we prove that when the inverse temperature is taken to be of the form ${\beta }_n=\stackrel{?}{\beta }{(b/s)}^{n/2}$ for $\stackrel{?}{\beta }>0$, the normalized partition function of the system converges weakly as $n\to \infty$ to a distribution $L\left(\stackrel{?}{\beta }\right)$ and does so universally with respect to the initial weight distribution. We prove the convergence using renormalization group type ideas rather than the standard Wiener chaos analysis. In the case $b=s$ we find a critical point in the behavior of the model when the inverse temperature is scaled as ${\beta }_n=\stackrel{?}{\beta }/n$; for an explicitly computable critical value ${\kappa }_b>0$ the variance of the normalized partition function converges to zero with large $n$ when $\stackrel{?}{\beta }\le {\kappa }_b$ and grows without bound when $\stackrel{?}{\beta }>{\kappa }_b$. Finally, we prove a central limit theorem for the normalized partition function when $\stackrel{?}{\beta }\le {\kappa }_b$.     

Estimates for eigenvalues of stochastic matrices

It is well-known that the eigenvalues of stochastic matrices lie in the unit circle and at least one of them has the value one. Let {1, r 2 , ··· , r N } be the eigenvalues of stochastic matrix X of size N × N . We will present in this paper a simple necessary and sufficient condition for X such that |r j | < 1, j = 2, ··· , N . Moreover, such condition can be very quickly examined by using some search algorithms from graph theory.     

Hypergraph list coloring and Euclidean Ramsey theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is s‐list colorable (or s‐choosable) if for any assignment of a list of s colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. We prove that for every positive integer r, there is a function d_r(s) such that no r‐uniform simple hypergraph with average degree at least d_r(s) is s‐list‐colorable. This extends a similar result for graphs, due to the first author, but does not give as good estimates of d_r(s) as are known for d₂(s), since our proof only shows that for each fixed r ≥ 2, d_r(s) ≤ 2 We use the result to prove that for any finite set of points X in the plane, and for any finite integer s, one can assign a list of s distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of X. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

对谱半径至多为$\sqrt[r]{2+\sqrt{5}}$的超图的分类研究

在本文,我们研究谱半径至多为$\sqrt[r]{2+\sqrt{5}}$的超图.我们得到此种超图必须具有一个基普结构,这与Woo-Neumaier在2007年对谱半径至多为$\frac{3}{2}\sqrt{2}$的图的分类结果类似.     

Novel scaling behavior of directed polymers: Disorder distribution with long tails

We study the problem of directed polymers (DP) on a square lattice. The distribution of disorder is assumed to be independent but non-Gaussian. We show that for distributions with a power-law tailP() 1/||¹⁺ , where>2, so that the mean and variance are well defined, the scaling exponentv of the DP model depends on in a continuous fashion.     

Hierarchies in φ‐spaces and applications

We establish some results on the Borel and difference hierarchies in φ‐spaces. Such spaces are the topological counterpart of the algebraic directed‐complete partial orderings. E.g., we prove analogs of the Hausdorff Theorem relating the difference and Borel hierarchies and of the Lavrentyev Theorem on the non‐collapse of the difference hierarchy. Some of our results generalize results of A. Tang for the space Pω. We also sketch some older applications of these hierarchies and present a new application to the question of characterizing the ω‐ary Boolean operations generating a given level of the Wadge hierarchy from the open sets. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fully dynamic recognition algorithm and certificate for directed cographs

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated; otherwise, a certificate is returned within the same complexity.     

Area Distribution for Directed Random Walks

We study the probability distribution for the area under a directed random walk in the plane. The walk can serve as a simple model for avalanches based on the idea that the front of an avalanche can be described by a random walk and the size is given by the area enclosed. This model captures some of the qualitative features of earthquakes, avalanches, and other self-organized critical phenomena in one dimension. By finding nonlinear functional relations for the generating functions we calculate directly the exponent in the size distribution law and find it to be 4/3.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.