ON possible Turán densities

The Turán density π(F) of a family F of k-graphs is the limit as n → ∞ of the maximum edge density of an F-free k-graph on n vertices. Let Π _∞ ^(k) consist of all possible Turán densities and let Π _fin ^(k) ? Π _∞ ^(k) be the set of Turán densities of finite k-graph families. Here we prove that Π _fin ^(k) contains every density obtained from an arbitrary finite construction by optimally blowing it up and using recursion inside the specified set of parts. As an application, we show that Π _fin ^(k) contains an irrational number for each k ≥ 3. Also, we show that Π _∞ ^(k) has cardinality of the continuum. In particular, Π _∞ ^(k) ≠ Π _fin ^(k) .     

Iteratedk-line graphs

For integersk≥2, thek-line graph L_k(G) of a graph G is defined as a graph whose vertices correspond to the complete subgraphs onk vertices in G with two distinct vertices adjacent if the corresponding complete subgraphs have 1 common vertices inG. We define iteratedk-line graphs byL _k ⁿ (G) ?L _k (L _k ^n?1 (G), whereL _k ⁰ (G) ?G. In this paper the iterated behavior of thek-line graph operator is investigated. It turns out that the behavior is quite different fork = 2 (the well-known line graph case),k = 3, and k≥4.     

The proof of a conjecture concerning the intersection of k-generalized Fibonacci sequences

For k ≥ 2, the k-generalized Fibonacci sequence (F _n ^(k) ) _n is defined by the initial values 0, 0, …, 0,1 (k terms) and such that each term afterwards is the sum of the k preceding terms. In 2005, Noe and Post conjectured that the only solutions of Diophantine equation F _m ^(k) = F _n ^(?) , with ? > k > 1, n > ? + 1, m > k + 1 are $(m,n,\ell ,k) = (7,6,3,2)and(12,11,7,3)$ . In this paper, we confirm this conjecture.     

Inversion complexity of self-correcting circuits for a certain sequence of boolean functions

The asymptotics L _k ^? (f ₂ ⁿ ) ?? n min{k+1, p} is obtained for the sequence of Boolean functions $f_2^n \left( {x_1 , \ldots ,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n}$ for any fixed k, p ?? 1 and growing n, here L _k ^? (f ₂ ⁿ ) is the inversion complexity of realization of the function f ₂ ⁿ by k-self-correcting circuits of functional elements in the basis B = {&, ?}, p is the weight of a reliable invertor.     

On the Brauer group of the product of a torus and a semisimple algebraic group

Let T be a torus (not assumed to be split) over a field F, and denote by nH _et ² (X,{ie375-1}) the subgroup of elements of the exponent dividing n in the cohomological Brauer group of a scheme X over the field F. We provide conditions on X and n for which the pull-back homomorphism nH _et ² (T,{ie375-2}) → _n H _et ² (X × _F T, {ie375-3}) is an isomorphism. We apply this to compute the Brauer group of some reductive groups and of non-singular affine quadrics. Apart from this, we investigate the p-torsion of the Azumaya algebra defined Brauer group of a regular affine scheme over a field F of characteristic p > 0.     

On the eigenvalues of the Sturm-Liouville operator with potentials from Sobolev spaces

We study the asymptotic behavior of the eigenvalues the Sturm-Liouville operator Ly = ?y″ + q(x)y with potentials from the Sobolev space W ₂ ^θ?1 , θ ≥ 0, including the nonclassical case θ ∈ [0, 1) in which the potential is a distribution. The results are obtained in new terms. Let s _2k (q) = λ _k ^1/2 (q) ? k, s _2k?1(q) = μ _k ^1/2 (q) ? k ? 1/2, where {λ _k } ₁ ^∞ and {μ _k } ₁ ^∞ are the sequences of eigenvalues of the operator L generated by the Dirichlet and Dirichlet-Neumann boundary conditions, respectively,. We construct special Hilbert spaces t ₂ ^θ such that the mapping F:W ₂ ^θ?1 →t ₂ ^θ defined by the equality F(q) = {s _n } ₁ ^∞ is well defined for all θ ≥ 0. The main result is as follows: for θ > 0, the mapping F is weakly nonlinear, i.e., can be expressed as F(q) = Uq + Φ(q), where U is the isomorphism of the spaces W ₂ ^θ?1 and t ₂ ^θ , and Φ(q) is a compact mapping. Moreover, we prove the estimate ∥Ф(q)∥_τ ≤ C∥q∥_θ?1, where the exact value of τ = τ(θ) > θ ? 1 is given and the constant C depends only on the radius of the ball ∥q∥_θ? ≤ R, but is independent of the function q varying in this ball.     

Jackson-type inequalities and widths of function classes in L 2

The sharp Jackson-type inequalities obtained by Taikov in the space L ₂ and containing the best approximation and the modulus of continuity of first order are generalized to moduli of continuity of kth order (k = 2, 3, ... ). We also obtain exact values of the n-widths of the function classes F(k, r, Φ) and F _k ^r (h), which are a generalization of the classes F(1, r, Φ) and F _k ^r (h) studied by Taikov.     

The number of 3-SAT functions

With G _k (n) denoting the number of functions of n Boolean variables definable by k-SAT formulas, we prove that G ₃(n) is asymptotic to 2 ⁿ +( ₃ ⁿ ). This is a strong form of the case k = 3 of a conjecture of Bollobás, Brightwell and Leader stating that for fixed k, log₂ G _k (n)~( _k ⁿ ).     

On the sum of powers of terms of a linear recurrence sequence

Let (F _n ) _n??0 be the Fibonacci sequence given by F _n+2 = F _n+1 + F _n , for n ?? 0, where F ₀ = 0 and F ₁ = 1. There are several interesting identities involving this sequence such as F _n ² + F _n+1 ² = F _2n+1, for all n ?? 0. In a very recent paper, Marques and Togbé proved that if F _n ^s + F _n+1 ^s is a Fibonacci number for all sufficiently large n, then s = 1 or 2. In this paper, we will prove, in particular, that if (G _m ) _m is a linear recurrence sequence (under weak assumptions) and G _n ^s + ... + G _n+k ^s ?? (G _m ) _m , for infinitely many positive integers n, then s is bounded by an effectively computable constant depending only on k and the parameters of G _m .     

Basis of graded identities of the superalgebra M 1,2(F)

Denote by Mat _k,l (F) the algebraM _n (F) of matrices of order n = k + l with the grading (Mat _k,l ⁰ (F),Mat _k,l ¹ (F)), where Mat _k,l ⁰ (F) admits the basis $$ \{ e_{ij} ,i \leqslant k,j \leqslant k\} \cup \{ e_{ij} ,i > k,j > k\} $$ and Mat _k,l ¹ (F) admits the basis $$ \{ e_{ij} ,i \leqslant k,j > k\} \cup \{ e_{ij} ,i > k,j \geqslant k\} . $$ . Denote byM _k,l (F) the Grassmann envelope of the superalgebra Mat _k,l (F). In the paper, bases of the graded identities of the superalgebras Mat_1,2(F) and M _1,2(F) are described.     

Ergodic dynamical systems over the cartesian power of the ring of p-adic integers

For any 1-lipschitz ergodic map F: ? _p ^k ? ? _p ^k , k >1 ∈ ?, there are 1-lipschitz ergodic map G: ? _p ? ? _p and two bijections H _k , T _{k, P} that $G = H_k \circ T_{k,P} \circ F \circ H_k^{ - 1} andF = H_k^{ - 1} \circ T_{k,P - 1} \circ G \circ H_k $ .     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Многомерные вариаци и множеств и их контин генции

LetE be a compact set inR ⁿ (n≧2), and denote byV ₀(E) the number of the components ofE. Letp=1,2, ...,n?1;k=0,1, ...,p, and $$V_k (E;n,p) = \int\limits_{\Omega _k^n } {V_0 (E \cap \tau )^{{{(n - p)} \mathord{\left/ {\vphantom {{(n - p)} {(n - k)}}} \right. \kern-\nulldelimiterspace} {(n - k)}}} d\mu _\tau ,}$$ whereΩ _k ⁿ is the set of all (n-k)-dimensional hyperplanesτ?R ⁿ anddμ _τ is the Haar measure on the spaceΩ _k ⁿ ; furthermore, let $$V_n (E;n,n - 1) = mes_n E.$$ . Theorem. Let E?Rⁿ, p=1, 2 ..., n?1, V_p+1(E;n,p)=0, and V_k(E; n, p)<∞ for k= =0,1, ..., p. Then the contingency of the set E at a point x∈E coincides with a certain p-dimensional hyperplane for almost all points x∈E in the sense of Hausdorff p-measure.     

Convolutions of random measures on compact groups

LetG be a compact group andM ₁(G) be the convolution semigroup of all Borel probability measures onG with the weak topology. We consider a stationary sequence {μ _n } _n=?∞ ^+∞ of random measures μ _n =μ _n (ω) inM ₁(G) and the convolutions $$v_{m,n} (\omega ) = \mu _m (\omega )* \cdots *\mu _{n - 1} (\omega ), m< n$$ and $$\alpha _n^{( + k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n,n + i} (\omega ),} \alpha _n^{( - k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n - i,n} (\omega )} $$ We describe the setsA _m ⁺ (ω) andA _n ⁺ (ω) of all limit points ofv _m,n(ω) asm→?∞ orn→+∞ and the setA _∞(ω) of its two-sided limit points for typical realizations of {μ _n (ω)} _n=?∞ ^+∞ . Using an appropriate random ergodic theorem we study the limit random measures ρ _n ^(±) (ω)=lim _k→∞ α _n ^(±k) (ω).     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

Almost everywhere divergent subsequences of Fourier sums of functions from φ(L) ∩ H 1 ω

For a gap sequence of natural numbers {n _k } _k=1 ^∞ , for a nondecreasing function φ: [0,+∞) → [0,+∞) such that φ(u) = o(u ln ln u) as u → ∞, and a modulus of continuity satisfying the condition (ln k)^?1 = O(ω(n _k ^?1 )), we present an example of a function F ∈ φ(L) ∩ H ₁ ^ω with an almost everywhere divergent subsequence {S _{n k} (F, x)} of the sequence of partial sums of the trigonometric Fourier series of the function F.     

The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2

It is shown that the conjunction complexity L _k ^& (f ₂ ⁿ ) of monotone symmetric Boolean functions \(f_2^n (x_1 , \ldots ,x_n ) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j\) realized by k-self-correcting circuits in the basis B = {&, ?} asymptotically equals to (k + 2)n for growing n providing the price of a reliable conjunctor is ≥ k + 2.     

On the boundedness of operators rearranging the Haar system in the spacesL p

Operators of the form Tπχ _n ^k =χ _n ^πn(k) where {χ _n ^k (t)} is the Haar system and π_n is a rearrangement of the numbers 1,2, ?.2ⁿ (n=1,2,?) are studied. Criterion for the boundedness of such operators from the spaceL _p intoL _p is obtained.     

Invariant Weighted Algebras ℒ p w (G)

The paper is devoted to weighted spaces ? _p ^w (G) on a locally compact group G. If w is a positive measurable function on G, then the space ? _p ^w (G), p ≥ 1, is defined by the relation ? _p ^w (G) = {f: fw ∈ ? _p (G)}. The weights w for which these spaces are algebras with respect to the ordinary convolution are treated. It is shown that, for p > 1, every sigma-compact group admits a weight defining such an algebra. The following criterion is proved (which was known earlier for special cases only): a space ? _p ^w (G) is an algebra if and only if the function w is semimultiplicative. It is proved that the invariance of the space ? _p ^w (G) with respect to translations is a sufficient condition for the existence of an approximate identity in the algebra ? _p ^w (G). It is also shown that, for a nondiscrete group G and for p > 1, no approximate identity of an invariant weighted algebra can be bounded.