General results on preferential attachment and clustering coefficient

This is a review paper that covers some recent results on the behavior of the clustering coefficient in preferential attachment networks and scale-free networks in general. The paper focuses on general approaches to network science. In other words, instead of discussing different fully specified random graph models, we describe some generic results which hold for classes of models. Namely, we first discuss a generalized class of preferential attachment models which includes many classical models. It turns out that some properties can be analyzed for the whole class without specifying the model. Such properties are the degree distribution and the global and average local clustering coefficients. Finally, we discuss some surprising results on the behavior of the global clustering coefficient in scale-free networks. Here we do not assume any underlying model.     

Universal inequalities in Ehrhart theory

In this paper, we show the existence of universal inequalities for the h*-vector of a lattice polytope P, that is, we show that there are relations among the coefficients of the h*-polynomial that are independent of both the dimension and the degree of P. More precisely, we prove that the coefficients h* ₁ and h* ₂ of the h*-vector (h* ₀, h* ₁,..., h* _d) of a lattice polytope of any degree satisfy Scott’s inequality if h* ₃ = 0.     

On vanishing coefficients of algebraic power series over fields of positive characteristic

Let K be a field of characteristic p>0 and let f(t ₁,…,t _d ) be a power series in d variables with coefficients in K that is algebraic over the field of multivariate rational functions K(t ₁,…,t _d ). We prove a generalization of both Derksen’s recent analogue of the Skolem–Mahler–Lech theorem in positive characteristic and a classical theorem of Christol, by showing that the set of indices (n ₁,…,n _d )∈? ^d for which the coefficient of \(t_{1}^{n_{1}}\cdots t_{d}^{n_{d}}\) in f(t ₁,…,t _d ) is zero is a p-automatic set. Applying this result to multivariate rational functions leads to interesting effective results concerning some Diophantine equations related to S-unit equations and more generally to the Mordell–Lang Theorem over fields of positive characteristic.     

(<Emphasis Type="Italic">m</Emphasis>,<Emphasis Type="Italic">r</Emphasis>)-central Riordan arrays and their applications

For integers m > r ≥ 0, Brietzke (2008) defined the (m, r)-central coefficients of an infinite lower triangular matrix G = (d, h) = (d_n,k)_n,k∈N as d_{mn+r,(m?1)n+r}, with n = 0, 1, 2,..., and the (m, r)-central coefficient triangle of G as

$${G^{\left( {m,r} \right)}} = {\left( {{d_{mn + r,\left( {m - 1} \right)n + k + r}}} \right)_{n,k \in \mathbb{N}}}.$$

It is known that the (m, r)-central coefficient triangles of any Riordan array are also Riordan arrays. In this paper, for a Riordan array G = (d, h) with h(0) = 0 and d(0), h′(0) ≠ 0, we obtain the generating function of its (m, r)-central coefficients and give an explicit representation for the (m, r)-central Riordan array G^(m,r) in terms of the Riordan array G. Meanwhile, the algebraic structures of the (m, r)-central Riordan arrays are also investigated, such as their decompositions, their inverses, and their recessive expressions in terms of m and r. As applications, we determine the (m, r)-central Riordan arrays of the Pascal matrix and other Riordan arrays, from which numerous identities are constructed by a uniform approach.

     

Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete ∑ ₃ ^{0, d} , and the second is m-complete ∑ ₃ ^{0, d} \∑ ₃ ^{0, d} in the universal computable numbering of computable structures for the language with one binary predicate.     

Depth and Stanley depth of the facet ideals of some classes of simplicial complexes

Let Δ _n,d (resp. Δ′ _n,d ) be the simplicial complex and the facet ideal I _n,d = (x ₁... x _d, x d?k+1... x _2d?k ,..., x _n?d+1... x _n ) (resp. J _n,d = (x ₁... x _d , x _d?k+1... x _2d?k ,..., x n?2d+2k+1... x _n?d+2k , x n?d+k+1... x n x ₁... x _k)). When d ≥ 2k + 1, we give the exact formulas to compute the depth and Stanley depth of quotient rings S/J _n,d and S/I _n,d ^t for all t ≥ 1. When d = 2k, we compute the depth and Stanley depth of quotient rings S/Jn,d and S/I _n,d , and give lower bounds for the depth and Stanley depth of quotient rings S/I _n,d ^t for all t ≥ 1.     

Diophantine inequality involving binary forms

Let d ? 3 be an integer, and set r = 2^d?1 + 1 for 3 ? d ? 4, \(\tfrac{{17}}{{32}} \cdot 2^d + 1\) for 5 ? d ? 6, r = d²+d+1 for 7 ? d ? 8, and r = d²+d+2 for d ? 9, respectively. Suppose that Φ _i (x, y) ∈ ?[x, y] (1 ? i ? r) are homogeneous and nondegenerate binary forms of degree d. Suppose further that λ₁, λ₂,..., λ _r are nonzero real numbers with λ₁/λ₂ irrational, and λ₁Φ₁(x₁, y₁) + λ₂Φ₂(x₂, y₂) + · · · + λ _r Φ _r (x _r , y _r ) is indefinite. Then for any given real η and σ with 0 < σ < 2^2?d, it is proved that the inequality

$$\left| {\sum\limits_{i = 1}^r {{\lambda _i}\Phi {}_i\left( {{x_i},{y_i}} \right) + \eta } } \right| < {\left( {\mathop {\max \left\{ {\left| {{x_i}} \right|,\left| {{y_i}} \right|} \right\}}\limits_{1 \leqslant i \leqslant r} } \right)^{ - \sigma }}$$

has infinitely many solutions in integers x₁, x₂,..., x _r , y₁, y₂,..., y _r . This result constitutes an improvement upon that of B. Q. Xue.

     

On the Wick theorem for mixtures of centered Gaussian distributions

We consider centered conditionally Gaussian d-dimensional vectors X with random covariance matrix Ξ having an arbitrary probability distribution law on the set of nonnegative definite symmetric d × d matrices M _d ⁺. The paper deals with the evaluation problem of mean values \( E\left[ {\prod\nolimits_{i = 1}^{2n} {\left( {{c_i},X} \right)} } \right] \) for c _i ∈ ? ^d , i = 1, …, 2n, extending the Wick theorem for a wide class of non-Gaussian distributions. We discuss in more detail the cases where the probability law ?(Ξ) is infinitely divisible, the Wishart distribution, or the inverse Wishart distribution. An example with Ξ \( = \sum\nolimits_{j = 1}^m {{Z_j}{\sum_j}} \), where random variables Z _j , j = 1, …, m, are nonnegative, and Σ _j ∈ M _d ⁺, j = 1, …, m, are fixed, includes recent results from Vignat and Bhatnagar, 2008.     

Membership of distributions of polynomials in the Nikolskii–Besov class

The main result of this paper asserts that the distribution density of any non-constant polynomial f(ξ₁,ξ₂,...) of degree d in independent standard Gaussian random variables ξ₁ (possibly, in infinitely many variables) always belongs to the Nikol’skii–Besov space B^1/d (R¹) of fractional order 1/d (see the definition below) depending only on the degree of the polynomial. A natural analog of this assertion is obtained for the density of the joint distribution of k polynomials of degree d, also with a fractional order that is independent of the number of variables, but depends only on the degree d and the number of polynomials. We also give a new simple sufficient condition for a measure on R^k to possess a density in the Nikol’skii–Besov class B^α(R)^k. This result is applied for obtaining an upper bound on the total variation distance between two probability measures on R^k via the Kantorovich distance between them and a certain Nikol’skii–Besov norm of their difference. Applications are given to estimates of distributions of polynomials in Gaussian random variables.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

On the sum of the L1 influences of bounded functions

Let f: {-1, 1}ⁿ → [-1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L₁ influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d³) for general functions and O(d²) for homogeneous functions. We improve on their results by providing a bound of d² for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.     

Commuting Krichever–Novikov differential operators with polynomial coefficients

Under study are some commuting rank 2 differential operators with polynomial coefficients. We prove that, for every spectral curve of the form w² = z³+c₂z2+c₁z+c₀ with arbitrary coefficients c_i, there exist commuting nonselfadjoint operators of orders 4 and 6 with polynomial coefficients of arbitrary degree.     

Riesz transform characterization of Hardy spaces associated with Schrödinger operators with compactly supported potentials

Let L=?Δ+V be a Schrödinger operator on ? ^d , d≥3. We assume that V is a nonnegative, compactly supported potential that belongs to L ^p (? ^d ), for some p>d /2. Let K _t be the semigroup generated by ?L. We say that an L ¹(? ^d )-function f belongs to the Hardy space \(H^{1}_{L}\) associated with L if sup?_t>0|K _t f| belongs to L ¹(? ^d ). We prove that \(f\in H^{1}_{L}\) if and only if R _j f∈L ¹(? ^d ) for j=1,…,d, where R _j =(?/? x _j )L ^?1/2 are the Riesz transforms associated with L.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

Dependence of Hilbert coefficients

Let M be a finitely generated module of dimension d and depth t over a Noetherian local ring (A, \({\mathfrak{m}}\)) and I an \({\mathfrak{m}}\)-primary ideal. In the main result it is shown that the last t Hilbert coefficients \({e_{d-t+1}(I,M),\ldots, e_{d}(I,M)}\) are bounded below and above in terms of the first d ? t + 1 Hilbert coefficients \({e_{0}(I,M),\ldots,e_{d-t}(I,M)}\) and d.     

Abelian Cayley Graphs of Given Degree and Diameter 2 and 3

Let CC _d,k be the largest possible number of vertices in a cyclic Cayley graph of degree d and diameter k, and let AC _d,k be the largest order in an Abelian Cayley graph for given d and k. We show that \({CC_{d,2} \geq \frac{13}{36} (d + 2)(d -4)}\) for any d= 6p?2 where p is a prime such that \({p \neq 13}\) , \({p \not\equiv 1}\) (mod 13), and \({AC_{d,3} \geq \frac{9}{128} (d + 3)^2(d - 5)}\) for d = 8q?3 where q is a prime power.     

Tong-type identity and the mean square of the error term for an extended Selberg class

In 1956, Tong established an asymptotic formula for the mean square of the error term of the summatory function of the Piltz divisor function d3(n). The aim of this paper is to generalize Tong's method to a class of Dirichlet series L(s) which satisfies a functional equation. Let a(n) be an arithmetical function related to a Dirichlet series L(s), and let E(x) be the error term of ′n xa(n). In this paper, after introducing a class of Diriclet series with a general functional equation(which contains the well-known Selberg class), we establish a Tong-type identity and a Tong-type truncated formula for the error term of the Riesz mean of the coefficients of this Dirichlet series L(s). This kind of Tong-type truncated formula could be used to study the mean square of E(x) under a certain assumption. In other words, we reduce the mean square of E(x) to the problem of finding a suitable constant σ*which is related to the mean square estimate of L(s). We shall represent some results of functions in the Selberg class of degrees 2–4.     

Resolution of veronese embedding of plane curves

Let C be a smooth (irreducible) curve of degree d in ?². Let ?² ? ?⁵ be the Veronese embedding and let I _C denote the homogeneous ideal of C on ?⁵. In this note we explicitly write down the minimal free resolution of I _C for d ≥ 2.     

Ramanujan complexes of type<Emphasis Type="Italic">Ã</Emphasis><Subscript><Emphasis Type="Italic">d</Emphasis></Subscript>

We define and construct Ramanujan complexes. These are simplicial complexes which are higher dimensional analogues of Ramanujan graphs (constructed in [LPS]). They are obtained as quotients of the buildings of typeà _d?1 associated with PGL _d (F) whereF is a local field of positive characteristic.     

One-element differential standard bases with respect to inverse lexicographical orderings

We give a simplified proof of the following fact: for all nonnegative integers n and d the monomial y _n ^d forms a differential standard basis of the ideal [y _n ^d ]. In contrast to Levi’s combinatorial proof, in this proof we use the Gröbner bases technique. Under some assumptions we prove the converse result: if an isobaric polynomial f forms a differential standard basis of [f], then f = y _n ^d .