On the Ramsey number of the triangle and the cube

The Ramsey number r(K ₃,Q _n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K _N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erd?s conjectured that r(K ₃,Q _n )=2 ⁿ⁺¹?1 for every n∈?, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K ₃,Q _n )?7000·2 ⁿ . Here we show that r(K ₃,Q _n )=(1+o(1))2 ⁿ⁺¹ as n→∞.     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

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).     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

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.     

On the densities of cliques and independent sets in graphs

Let r; s≥2 be integers. Suppose that the number of blue r-cliques in a red/blue coloring of the edges of the complete graph K _n is known and fixed. What is the largest possible number of red s-cliques under this assumption? The well known Kruskal-Katona theorem answers this question for r = 2 or s = 2. Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

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.     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Meromorphic Solutions for a Class of Differential Equations and Their Applications

In this note, we study the admissible meromorphic solutions for algebraic differential equation fⁿf' + P_n?1(f) = R(z)e^α(z), where P_n?1(f) is a differential polynomial in f of degree ≤ n ? 1 with small function coefficients, R is a non-vanishing small function of f, and α is an entire function. We show that this equation does not possess any meromorphic solution f(z) satisfying N(r, f) = S(r, f) unless P_n?1(f) ≡ 0. Using this result, we generalize a well-known result by Hayman.     

Counting sets with small sumset and applications

We study the number of k-element sets A? {1,...,N} with |A+A| ≤ K|A| for some (fixed) K > 0. Improving results of the first author and of Alon, Balogh, Samotij and the second author, we determine this number up to a factor of 2 ^{o ( k )} N ^{o (1)} for most N and k. As a consequence of this and a further new result concerning the number of sets A??/N? with |A+A| ≤ c|A|², we deduce that the random Cayley graph on ?/N? with edge density ½ has no clique or independent set of size greater than (2+o(1)) log₂ N, asymptotically the same as for the Erd?s-Rényi random graph. This improves a result of the first author from 2003 in which a bound of 160log₂ N was obtained. As a second application, we show that if the elements of A ? ? are chosen at random, each with probability 1/2, then the probability that A+A misses exactly k elements of ? is equal to (2+O(1))^?k/2 as k → ∞.     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

Two-weighted estimates for generalized fractional maximal operators on non-homogeneous spaces

Let μ be a nonnegative Borel measure on R ^d satisfying that μ(Q) ? l(Q)ⁿ for every cube Q ? R ⁿ , where l(Q) is the side length of the cube Q and 0 < n ? d.We study the class of pairs of weights related to the boundedness of radial maximal operators of fractional type associated to a Young function B in the context of non-homogeneous spaces related to the measure μ. Our results include two-weighted norm and weak type inequalities and pointwise estimates. Particularly, we give an improvement of a two-weighted result for certain fractional maximal operator proved in W.Wang, C. Tan, Z. Lou (2012).     

Homogenization of the Dirichlet problem for elliptic and parabolic systems with periodic coefficients

Let O ? R ^d be a bounded domain of class C ^1,1. Let 0 < ε - 1. In L ₂(O;C ⁿ ) we consider a positive definite strongly elliptic second-order operator B _D,ε with Dirichlet boundary condition. Its coefficients are periodic and depend on x/ε. The principal part of the operator is given in factorized form, and the operator has lower order terms. We study the behavior of the generalized resolvent (B _D,ε ? ζQ ₀(·/ε))^?1 as ε → 0. Here the matrix-valued function Q ₀ is periodic, bounded, and positive definite; ζ is a complex-valued parameter. We find approximations of the generalized resolvent in the L ₂(O;C ⁿ )-operator norm and in the norm of operators acting from L ₂(O;C ⁿ ) to the Sobolev space H ¹(O;C ⁿ ) with two-parameter error estimates (depending on ε and ζ). Approximations of the generalized resolvent are applied to the homogenization of the solution of the first initial-boundary value problem for the parabolic equation Q ₀(x/ε)? _t v _ε (x, t) = ?(B _D,ε v _ε )(x, t).     

Equiconvergence of expansions in multiple Fourier series and in fourier integrals with “lacunary sequences of partial sums”

We investigate the equiconvergence on T^N = [?π, π)^N of expansions in multiple trigonometric Fourier series and in the Fourier integrals of functions f ∈ L_p(T^N) and g ∈ L_p(R^N), p > 1, N ≥ 3, g(x) = f(x) on T^N, in the case where the “partial sums” of these expansions, i.e., S_n(x; f) and J_α(x; g), respectively, have “numbers” n ∈ Z^N and α ∈ R^N (n_j = [α_j], j = 1,..., N, [t] is the integral part of t ∈ R¹) containing N ? 1 components which are elements of “lacunary sequences.”     

On the Nitsche conjecture for harmonic mappings in ℝ<Superscript>2</Superscript> and ℝ<Superscript>3</Superscript>

We give the new inequality related to the J. C. C. Nitsche conjecture (see [6]). Moreover, we consider the two- and three-dimensional case. LetA(r, 1)={z:r<|z|<1}. Nitsche's conjecture states that if there exists a univalent harmonic mapping from an annulusA(r, 1), to an annulusA(s, 1), thens is at most 2r/(r ²+1).Lyzzaik's result states thats<t wheret is the length of the Grötzsch's ring domain associated withA(r, 1) (see [5]). Weitsman's result states thats≤1/(1+1/2(r logr)²) (see [8]).Our result for two-dimensional space states thats≤1/(1+1/2 log² r) which improves Weitsman's bound for allr, and Lyzzaik's bound forr close to 1. For three-dimensional space the result states thats≤1/(r?logr).     

Sieve Functions in Arithmetic Bands,II

An arithmetic function f is called a sieve function of range Q if its Eratosthenes transform g = f * μ is supported in [1,Q] ∩ N, where g(q) ? _ε q ^ε (?ε > 0). We continue our study of the distribution of f(n) over short arithmetic bands, n ≡ ar + b (mod q), with n ∈ (N,2N] ∩ N, 1 ≤ a ≤ H = o(N) and r,b ∈ Z such that g:c:d:(r,q) = 1. In particular, the optimality of some results is discussed.     

Variational Problems with Unilateral Pointwise Functional Constraints in Variable Domains

We consider a sequence of convex integral functionals F_s: W¹,^p(Ω_s) → ? and a sequence of weakly lower semicontinuous and generally nonintegral functionals G_s: W¹,^p(Ω_s) → ?, where {Ω_s} is a sequence of domains in ?ⁿ contained in a bounded domain Ω ? ?ⁿ (n ≥ 2) and p > 1. Along with this, we consider a sequence of closed convex sets V_s = {v ∈ W¹,^p(Ω_s): v ≥ K_s(v) a.e. in Ω_s}, where K_s is a mapping from the space W¹,^p(Ω_s) to the set of all functions defined on Ω_s. We establish conditions under which minimizers and minimum values of the functionals F_s + G_s on the sets V_s converge to a minimizer and the minimum value of a functional on the set V = {v ∈ W¹,^p(Ω): v ≥ K(v) a.e. in Ω}, where K is a mapping from the space W¹,^p(Ω) to the set of all functions defined on Ω. These conditions include, in particular, the strong connectedness of the spaces W¹,^p(Ω_s) with the space W¹,^p(Ω), the condition of exhaustion of the domain Ω by the domains Ω_s, the Γ-convergence of the sequence {F_s} to a functional F: W¹,^p(Ω) → ?, and a certain convergence of the sequence {G_s} to a functional G: W¹,^p(Ω) → ?. We also assume some conditions characterizing both the internal properties of the mappings K_s and their relation to the mapping K. In particular, these conditions admit the study of variational problems with irregular varying unilateral obstacles and with varying constraints combining the pointwise dependence and the functional dependence of the integral form.     

On Excess-time Correlated Cumulative Processes

In this paper a class of correlated cumulative processes, B _s (t) = ∑^N(t)_i=1 H _s (X _i )X _i , is studied with excess level increments X _i ?s, where {N(t), t ?0} is the counting process generated by the renewal sequence T _n , T _n and X _n are correlated for given n, H _s (t) is the Heaviside function and s?0 is a given constant. Several useful results, for the distributions of B _s (t), and that of the number of excess (non-excess) increments on (0, t) and the corresponding means, are derived. First passage time problems are also discussed and various asymptotic properties of the processes are obtained. Transform results, by applying a flexible form for the joint distribution of correlated pairs (T _n , X _n ) are derived and inverted. The case of non-excess level increments, X _i < s, is also considered. Finally, applications to known stochastic shock and pro-rata warranty models are given.