Monochromatic subgraphs in randomly colored graphons

Let $T(H,G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H,G_n)$, when ${\left\{G_n\right\}}_{n\ge 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H,G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H,G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s,K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.     

Sharp Reilly-type inequalities for a class of elliptic operators on submanifolds

Let M be an $n(>2)$-dimensional closed orientable submanifold in an $(n+p)$-dimensional space form ${\mathbb{R}}^{n+p}(c)$. We obtain an optimal upper bound for the second eigenvalue of a class of elliptic operators on M defined by $L_{T}f=-\text{div}(T\mathrm{\nabla }f)$, where T is a general symmetric, positive definite and divergence-free $(1,1)$-tensor on M. The upper bound is given in terms of an integration involving tr T and $|H_T{|}^2$, where tr T is the trace of the tensor T and $H_T={\sum }_{i=1}^{n}A(T{e}_i,e_i)$ is a normal vector field associated with T and the second fundamental form A of M. Furthermore, we give the sufficient and necessary conditions when the upper bound is attained. Our main theorem can be viewed as an extension of the famous “Reilly inequality”. The operator $L_T$ can be regarded as a natural generalization of the well-known operator $L_r$ which is the linearized operator of the first variation of the $(r+1)$-th mean curvature for hypersurfaces in a space form. As applications of our main theorem, we generalize the results of Grosjean [17] and Li–Wang [20] in codimension one to arbitrary codimension.     

Symmetrizers for Schur superalgebras

For the Schur superalgebra $S=S(m|n,r)$ over a ground field K of characteristic zero, we define the symmetrizer $T^{\lambda }[i:j]$ of the ordered pairs of tableaux $(T_i,T_j)$ of the shape λ. We show that the K-span $A_{\lambda ,K}$ of all symmetrizers $T^{\lambda }[i:j]$ has a basis consisting of $T^{\lambda }[i:j]$ for $T_i$ and $T_j$ semistandard. In particular, $A_{\lambda ,K}\ne 0$ if and only if λ is an $(m|n)$-hook partition. In this case, the S-superbimodule $A_{\lambda ,K}$ is identified as $D_{\lambda }{?}_K{D}_{\lambda }^o$, where $D_{\lambda }$ and $D_{\lambda }^o$ are left and right irreducible S-supermodules of the highest weight λ.We define modified symmetrizers $T^{\lambda }\{i:j\}$ and show that their $\mathbb{Z}$-span forms a $\mathbb{Z}$-form $A_{\lambda ,\mathbb{Z}}$ of $A_{\lambda ,\mathbb{Q}}$. We show that every modified symmetrizer $T^{\lambda }\{i:j\}$ is a $\mathbb{Z}$-linear combination of modified symmetrizers $T^{\lambda }\{i:j\}$ for $T_i,T_j$ semistandard. Using modular reduction to a field K of characteristic $p>2$, we obtain that $A_{\lambda ,K}$ has a basis consisting of modified symmetrizers $T^{\lambda }\{i:j\}$ for $T_i$ and $T_j$ semistandard.     

Maximal displacement of a supercritical branching random walk in a time-inhomogeneous random environment

The behavior of the maximal displacement of a supercritical branching random walk has been a subject of intense studies for a long time. But only recently the case of time-inhomogeneous branching has gained focus. The contribution of this paper is to analyze a time-inhomogeneous model with two levels of randomness. In the first step a sequence of branching laws is sampled independently according to a distribution on the set of point measures’ laws. Conditionally on the realization of this sequence (called environment) we define a branching random walk and find the asymptotic behavior of its maximal particle. It is of the form $V_n?\phi logn+o_{\mathbf{P}}(logn)$, where $V_n$ is a function of the environment that behaves as a random walk and $\phi >0$ is a deterministic constant, which turns out to be bigger than the usual logarithmic correction of the homogeneous branching random walk.     

Common values of a class of linear recurrences

Let $\left(a_n\right),\left(b_n\right)$ be linear recursive sequences of integers with characteristic polynomials $A\left(X\right),B\left(X\right)\in \mathbb{Z}\left[X\right]$ respectively. Assume that $A\left(X\right)$ has a dominating and simple real root $\alpha$, while $B\left(X\right)$ has a pair of conjugate complex dominating and simple roots $\beta ,\stackrel{?}{\beta }$. Assume further that $\alpha ,\beta ,\alpha /\beta$ and $\stackrel{?}{\beta }/\beta$ are not roots of unity and $\delta =log\left|\beta \right|/log\left|\alpha \right|\in \mathbb{Q}$. Then there are effectively computable constants $c_0,c_1>0$ such that the inequality $|a_n?b_m|>{\left|a_n\right|}^{1?\left(c_0{log}^{2}n\right)/n}$holds for all $n,m\in {\mathbb{Z}}_{\ge 0}^2$ with $max\{n,m\}>c_1$. We present $c_0$ explicitly.     

A generalization of Schönemann’s theorem via a graph theoretic method

Recently, Grynkiewicz et al. (2013), using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence $a_1{x}_1+?+a_k{x}_k\equiv b(modn)$, where $a_1,\dots ,a_k,b,n$ ($n\ge 1$) are arbitrary integers, has a solution $〈x_1,\dots ,x_k〉\in {\mathbb{Z}}_n^k$ with all $x_i$ distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Schönemann almost two centuries ago(!) but his result seems to have been forgotten. Schönemann (1839), proved an explicit formula for the number of such solutions when $b=0$, $n=p$ a prime, and ${\sum }_{i=1}^k{a}_i\equiv 0(modp)$ but ${\sum }_{i\in I}{a}_i?\equiv 0(modp)$ for all $0?\ne I??\{1,\dots ,k\}$. In this paper, we generalize Schönemann’s theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems.