On the KŁR conjecture in random graphs

The K?R conjecture of Kohayakawa, ?uczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G _n,p , for sufficiently large p:= p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and Rödl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications.     

A generalized Turán problem in random graphs

We study a generalization of the Turán problem in random graphs. Given graphs T and H, let ex(G(n,p),T,H) be the largest number of copies of T in an H‐free subgraph of G(n,p). We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every H and every 2‐balanced T. Our results in the case when m₂(H) > m₂(T) are a natural generalization of the Erd?s‐Stone theorem for G(n,p), proved several years ago by Conlon‐Gowers and Schacht; the case T = K_m was previously resolved by Alon, Kostochka, and Shikhelman. The case when m₂(H) ≤ m₂(T) exhibits a more complex behavior. Here, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of H with copies of T and the typical value(s) of ex(G(n,p),T,H) are given by solutions to deterministic hypergraph Turán‐type problems that we are unable to solve in full generality.     

Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

A rainbow blow‐up lemma

We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn‐bounded edge colorings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow‐up lemma can be used to transfer the bandwidth theorem of Böttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn‐bounded edge colorings. Kim, Kühn, Kupavskii, and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow‐up lemma given by Rödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan.     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

Mantel's theorem for random graphs

For a graph G, denote by t(G) (resp. b(G)) the maximum size of a triangle‐free (resp. bipartite) subgraph of G. Of course for any G, and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e., for what p = p(n)) is the “Erd?s‐Rényi” random graph G = G(n,p) likely to satisfy t(G) = b(G)? We show that this is true if for a suitable constant C, which is best possible up to the value of C. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 59–72, 2015     

Local limit theorems for occupancy models

We present a rather general method for proving local limit theorems, with a good rate of convergence, for sums of dependent random variables. The method is applicable when a Stein coupling can be exhibited. Our approach involves both Stein's method for distributional approximation and Stein's method for concentration. As applications, we prove local central limit theorems with rate of convergence for the number of germs with d neighbors in a germ‐grain model, and the number of degree‐d vertices in an Erd?s‐Rényi random graph. In both cases, the error rate is optimal, up to logarithmic factors.     

Almost sure central limit theorems for random fields

A general almost sure limit theorem is presented for random fields. It is applied to obtain almost sure versions of some (functional) central limit theorems. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Gigantic component in random distance graphs of special form

We consider the problem of threshold probability for the existence of a gigantic component in a certain series of random distance graphs. The results obtained generalize the classical Erd?s-Rényi theorems in the case of geometric graphs of special form.     

Local Limit Theorems for Sequences of Simple Random Walks on Graphs

In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.      

Asymptotic Normality of Kernel Type Density Estimators for Random Fields

Kernel type density estimators are studied for random fields. It is proved that the estimators are asymptotically normal if the set of locations of observations become more and more dense in an increasing sequence of domains. It turns out that in our setting the covariance structure of the limiting normal distribution can be a combination of those of the continuous parameter and the discrete parameter cases. The proof is based on a new central limit theorem for α-mixing random fields. Simulation results support our theorems. Final version 29 October 2004     

The Erdős-Ko-Rado theorem for finite affine spaces

In [W.N. Hsieh, Intersection theorems for finite vector spaces, Discrete Math. 12 (1975) 1–16], Hsieh obtained the Erd?s-Ko-Rado theorem for finite vector spaces. This paper generalizes Hsieh’s result and obtains the Erd?s-Ko-Rado theorem for finite affine spaces.     

弱拓扑下的非线性随机积分和微分方程组的解*

在本文中,我们首先对具有随机定义域的弱连续随机算子组证明了一个Darbo型随机不动点定理.利用这一定理,我们对Banach空间中关于弱拓扑的非线性随机Volterra积分方程组给出了随机解的存在性准则.作为应用,我们得到了非线性随机微分方程组的Canchy问题弱随机解的存在定理.也得到了这些随机方程组在Banach空间中关于弱拓扑的极值随机解的存在性和随机比较结果.我们的定理改进和推广了Szep,Mitchell－Smith,Cramer－Lakshmikantham,Lakshmikantham-Leela和丁的相应结果.     

Random sum-free subsets of abelian groups

We characterize the structure of maximum-size sum-free subsets of a random subset of an abelian group G. In particular, we determine the threshold above which, with high probability as |G| → ∞, each such subset is contained in some maximum-size sum-free subset of G, whenever q divides |G| for some (fixed) prime q with q ≡ 2 (mod 3). Moreover, in the special case G = ?_2n , we determine the sharp threshold for the above property. The proof uses recent ‘transference’ theorems of Conlon and Gowers, together with stability theorems for sum-free sets of abelian groups.     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

Generalized KKM type theorems in FC-spaces with applications (II)

This paper is a continuum of the preceding paper of author. By applying a coincidence theorem in noncompact FC-space without any convexity structure due to author, a new KKM type theorem is first proved under noncompact setting of FC-spaces. The equivalent relation between the coincidence theorem and the KKM type theorem is also established. As applications of the KKM type theorem, we establish some new existence theorems of solutions for three classes of generalized vector equilibrium problems under noncompact setting of FC-spaces. These theorems improve and generalize many known results in literature.     

Classical large deviation theorems on complete Riemannian manifolds

We generalize classical large deviation theorems to the setting of complete, smooth Riemannian manifolds. We prove the analogue of Mogulskii’s theorem for geodesic random walks via a general approach using viscosity solutions for Hamilton–Jacobi equations. As a corollary, we also obtain the analogue of Cramér’s theorem. The approach also provides a new proof of Schilder’s theorem. Additionally, we provide a proof of Schilder’s theorem by using an embedding into Euclidean space, together with Freidlin–Wentzell theory.     

A probabilistic approach to the leader problem in random graphs

We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erd?s‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes ?uczak's result for the Erd?s‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.     

随机单调算子的满射性及应用

研究Banach空间中的随机单调算子,建立了连续随机单调算子的随机锐角原理、随机满射定理、随机双射定理及Hilbert空间上的一类连续随机算子的新的随机不动点定理,并应用随机强单调算子理论讨论了随机Hammerstein积分方程随机解的存在唯一性.     

Multiparameter ratio ergodic theorems for semigroups

After one-parameter treatment of ratio ergodic theorems for semigroups, we formulate the Sucheston a.e. convergence principle of continuous parameter type. This principle plays an effective role in proving some multiparameter generalizations of Chacon?s type continuous ratio ergodic theorems for semigroups and of Jacobs? type continuous random ratio ergodic theorems for quasi-semigroups. In addition, a continuous analogue of the Brunel–Dunford–Schwartz ergodic theorem is given of sectorially restricted averages for a commutative family of semigroups. We also formulate a local a.e. convergence principle of Sucheston?s type. The local convergence principle is effective in proving multiparameter local ergodic theorems. In fact, a multiparameter generalization of Akcoglu–Chacon?s local ratio ergodic theorem for semigroups of positive linear contractions on _L1$L_1$ is proved. Moreover, some multiparameter martingale theorems are obtained as applications of convergence principles.