Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Non-triviality of a product in the Adams <Emphasis Type="Italic">E</Emphasis> <Subscript>2</Subscript>-term

Let p be a prime greater than five and A the mod p Steenrod algebra. In this paper, we prove that \(h_n h_m \tilde \delta _{s + 4} \in Ext_A^{s + 6,t(s,n,m) + s} (Z/p,Z/p)\) is nontrivial in the Adams E₂-term when m ≥ n + 2 ≥ 7 and 0 ≤ s < p ? 4, and trivial in the Adams E₂-term when m ≥ n + 2 = 6 and 0 ≤ s < p ? 4, where \(\tilde \delta _{s + 4} \) stands for the fourth Greek letter element and t(s, n, m) = 2(p ? 1)[(s + 1) + (s + 2)p + (s + 3)p² + (s + 4)p³ + pⁿ + p^m].     

Hyperbolic Chevalley groups on ℂ<Superscript>2</Superscript>

Let Γ ? U (1, 1) be the subgroup generated by the complex reflections. Suppose that Γ acts discretely on the domain K = {(z ₁, z ₂) ∈ ?² ||z ₁|² ? |z ₂|² < 0} and that the projective group PΓ acts on the unit disk B = {|z ₁/z ₂| < 1} as a Fuchsian group of signature (n ₁, ..., n _s ), s ? 3, n _i ? 2. For such groups, we prove a Chevalley type theorem, i.e., find a necessary and sufficient condition for the quotient space K/Γ to be isomorphic to ?² ? {0}.     

Disjoint cliques in claw-free graphs

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_1,3. Let s and k be two integers with 0 ≤ s ≤ k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n ≥ 3s+4(k?s) and d(x)+d(y) ≥ n?2s+2k+1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K₃s and k ? s disjoint K₄s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.     

Some estimates for commutators of Riesz transform associated with Schrödinger type operators

Let L₁ = ?Δ + V be a Schr:dinger operator and let L² = (?Δ)² + V² be a Schrödinger type operator on ?ⁿ (n ? 5), where V≠ 0 is a nonnegative potential belonging to certain reverse Hölder class B_s for s ? n/2. The Hardy type space \(H_{{L_2}}^1\) is defined in terms of the maximal function with respect to the semigroup \(\left\{ {{e^{ - t{L_2}}}} \right\}\) and it is identical to the Hardy space \(H_{{L_1}}^1\) established by Dziubański and Zienkiewicz. In this article, we prove the L^p-boundedness of the commutator R_b = bRf - R(bf) generated by the Riesz transform \(R = {\nabla ^2}L_2^{ - 1/2}\), where \(b \in BM{O_\theta }(\varrho )\), which is larger than the space BMO(?ⁿ). Moreover, we prove that R_b is bounded from the Hardy space \(H_{\mathcal{L}_1 }^1 \) into weak \(L_{weak}^1 (\mathbb{R}^n )\).     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

Parabolic equation with a singular potential

We study the existence of a nonnegative generalized solution of an initial-boundary value problem for the heat equation with a singular potential in an arbitrary bounded domain Ω ? R ⁿ , n ≥ 3, containing the unit ball. We show that if the condition ∝ _Ω V ^n/2+s |x| ^s dx ≤ c _n is satisfied for some s ≥ 0 and c _n = c _n (n, s, Ω) > 0, then the problem in question has a nonnegative solution.     

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.     

Universal zero-one <Emphasis Type="Italic">k</Emphasis>-law

The limit probabilities of first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. For any positive integer k ≥ 4 and any rational number t/s ∈ (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n→∞) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds.     

Harmonic analysis associated with a discrete Laplacian

It is well known that the fundamental solution of

$${u_t}\left( {n,t} \right) = u\left( {n + 1,t} \right) - 2u\left( {n,t} \right) + u\left( {n - 1,t} \right),n \in \mathbb{Z},$$

with u(n, 0) = δ _nm for every fixed m ∈ Z is given by u(n, t) = e ^?2t I _n?m (2t), where I _k (t) is the Bessel function of imaginary argument. In other words, the heat semigroup of the discrete Laplacian is described by the formal series W _t f(n) = Σ _m∈Z e ^?2t I _n?m (2t)f(m). This formula allows us to analyze some operators associated with the discrete Laplacian using semigroup theory. In particular, we obtain the maximum principle for the discrete fractional Laplacian, weighted ? ^p (Z)-boundedness of conjugate harmonic functions, Riesz transforms and square functions of Littlewood-Paley. We also show that the Riesz transforms essentially coincide with the so-called discrete Hilbert transform defined by D. Hilbert at the beginning of the twentieth century. We also see that these Riesz transforms are limits of the conjugate harmonic functions. The results rely on a careful use of several properties of Bessel functions.

     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.     

A class of constacyclic codes over a finite field-II

Let \(\mathbb{F}_q\) be a finite field with q = p ^m elements, where p is any prime and m ≥ 1. In this paper, we explicitly determine all the μ-constacyclic codes of length ? ⁿ over \(\mathbb{F}_q\), where ? is an odd prime coprime to p and the order of μ is a power of ?. All the repeated-root λ- constacyclic codes of length ? ⁿ p ^s over \(\mathbb{F}_q\) are also determined for any nonzero λ in \(\mathbb{F}_q\). As examples all the λ-constacyclic codes of length 3 ⁿ p ^s over \(\mathbb{F}_q\) for p = 5, 7, 11, 19 for n ≥ 1, s ≥ 1 are derived. We also obtain all the self-orthogonal negacyclic codes of length ? ⁿ over \(\mathbb{F}_q\) when q is odd prime power and give some illustrative examples.     

On homogenization for non-self-adjoint locally periodic elliptic operators

In this note we consider the homogenization problem for a matrix locally periodic elliptic operator on R ^d of the form A ^ε = ?divA(x, x/ε)?. The function A is assumed to be Hölder continuous with exponent s ∈ [0, 1] in the “slow” variable and bounded in the “fast” variable. We construct approximations for (A ^ε ? μ)^?1, including one with a corrector, and for (?Δ) ^s/2(A ^ε ? μ)^?1 in the operator norm on L ₂(R ^d ) ⁿ . For s ≠ 0, we also give estimates of the rates of approximation.     

Embedding of Sobolev spaces with limit exponent revisited

An embedding of the Sobolev spaces W _p ^s (? ⁿ ) in Lizorkin-type spaces of locally integrable functions of smoothness zero is obtained; a similar assertion for Riesz and Bessel potentials is presented. The embedding theorem is extended to Sobolev spaces on irregular domains in n-dimensional Euclidean space. The statement of the theorem depends on geometric parameters of the domain of functions.     

Holomorphic factorization of polynomials

We give necessary and sufficient conditions for a holomorphic factorization of an irreducible polynomial P(s, λ), s ∈ Cⁿ, λ ∈ C, in a domain Ω ? Cⁿ which is connected with the ordering of the real part of the roots of the equation P(s, λ) = 0, s ∈ Ω.     

Proof of the Erdős matching conjecture in a new range

Let s > k ≧ 2 be integers. It is shown that there is a positive real ε = ε(k) such that for all integers n satisfying (s + 1)k ≦ n < (s + 1)(k + ε) every k-graph on n vertices with no more than s pairwise disjoint edges has at most \(\left( {\begin{array}{*{20}{c}} {\left( {s + 1} \right)k - 1} \\ k \end{array}} \right)\) edges in total. This proves part of an old conjecture of Erd?s.     

Characterizations of symmetrized polydisc

Let Γ_n, n ≥ 2, denote the symmetrized polydisc in ?ⁿ, and Γ₁ be the closed unit disc in ?. We provide some characterizations of elements in Γ_n. In particular, an element (s₁,..., s_n?1, p) ∈ ?ⁿ is in Γ_n if and only if \({s_j} = {\beta _j} + \overline {{\beta _{n - j}}}p\), j = 1,..., n ? 1, for some (β₁,..., β_n?1) ∈ Γ_n?1, and |p| ≤ 1.     

On the Distribution of Zero Sets of Holomorphic Functions

Let M be a subharmonic function with Riesz measure ν _M in a domain D in the n-dimensional complex Euclidean space ? _n , and let f be a nonzero function that is holomorphic in D, vanishes on a set Z ? D, and satisfies |f| ? expM on D. Then restrictions on the growth of ν _M near the boundary of D imply certain restrictions on the dimensions or the area/volume of Z. We give a quantitative study of this phenomenon in the subharmonic framework.