A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

Peixoto graph of Morse-Smale diffeomorphisms on manifolds of dimension greater than three

Let M ⁿ be a closed orientable manifold of dimension greater than three and G ₁(M ⁿ ) be the class of orientation-preserving Morse-Smale diffeomorphisms on M ⁿ such that the set of unstable separatrices of every f ∈ G ₁(M ⁿ ) is one-dimensional and does not contain heteroclinic orbits. We show that the Peixoto graph is a complete invariant of topological conjugacy in G ₁(M ⁿ ).     

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→∞.     

Universal varieties of quasi-Stone algebras

In this paper, we are mainly concerned with semicontinuity of complete lattices and their distributive reflections, introduced by Rav in 1989. We prove that for a complete lattice L, the distributive reflection L_d is isomorphic to the lattice of all radicals determined by principal ideals of L in the set-inclusion order, obtaining a method to depict the distributive reflection of a given lattice. It is also proved that if a complete lattice L is semicontinuous and every semiprime element x ∈ L is the largest in d(x), then L_d is continuous whenever the distributive reflector d is Scott continuous. We construct counterexamples to confirm a conjecture and solve two open problems posed by Zhao in 1997.     

On the Completeness of Products of Harmonic Functions and the Uniqueness of the Solution of the Inverse Acoustic Sounding Problem

It is proved that the family of all pairwise products of regular harmonic functions on D and of the Newtonian potentials of points on the line L ? Rⁿ is complete in L₂(D), where D is a bounded domain in Rⁿ, n ≥ 3, such that \(\bar D\) ∩ L = ?. This result is used in the proof of uniqueness theorems for the inverse acoustic sounding problem in R³.     

On the Skeleton of the Polytope of Pyramidal Tours

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR(n) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K _n . The skeleton of PYR(n) is the graph whose vertex set is the vertex set of PYR(n) and the edge set is the set of geometric edges or one-dimensional faces of PYR(n). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR(n). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR(n) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR(n) is Θ(n²). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

Nonasymptotic approach to Bayesian semiparametric inference

The classical semiparametric Bernstein–von Mises (BvM) results is reconsidered in a non-classical setup allowing finite samples and model misspecication. We obtain an upper bound on the error of Gaussian approximation of the posterior distribution for the target parameter which is explicit in the dimension of the target parameter and in the dimension of sieve approximation of the nuisance parameter. This helps to identify the so called critical dimension p_n of the sieve approximation of the full parameter for which the BvM result is applicable. If the bias induced by sieve approximation is small and dimension of sieve approximation is smaller then critical dimension than the BvM result is valid. In the important i.i.d. and regression cases, we show that the condition “p_n²q/n is small”, where q is the dimension of the target parameter and n is the sample size, leads to the BvM result under general assumptions on the model.     

On the maximum rank of a real binary form

We show that a real binary form f of degree n has n distinct real roots if and only if for any \({(\alpha,\beta)\in\mathbb{R}^2{\setminus}\{0\}}\) all the forms αf _x + βf _y have n ? 1 distinct real roots. This answers to a question of Comon and Ottaviani (On the typical rank of real binary forms, available at arXiv:math/0909.4865, 2009), and allows to complete their argument to show that f has symmetric rank n if and only if it has n distinct real roots.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).     

Depth of Boolean functions over an arbitrary infinite basis

Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer n as the minimal depth D _B (n) of the circuits sufficient to realize every Boolean function on n variables over a basis B. It is shown that, for each infinite basis B, either there exists a constant β ? 1 such that D _B (n) = β for all sufficiently large n or there exist an integer constant γ ? 2 and a constant δ such that log _γ n ? D _B (n) ? log _γ n + δ for all n.     

A Note on MDS Codes, <Emphasis Type="Italic">n</Emphasis>-Arcs and Complete Designs

A generalized incidence matrix of a design over GF(q) is any matrix obtained from the (0, 1)-incidence matrix by replacing ones with nonzero elements from GF(q). The dimension d _q of a design D over GF(q) is defined as the minimum value of the q-rank of a generalized incidence matrix of D. It is proved that the dimension d _q of the complete design on n points having as blocks all w-subsets, is greater that or equal to n ? w + 1, and the equality d _q = n ? w + 1 holds if and only if there exists an [n, n ? w + 1, w] MDS code over GF(q), or equivalently, an n-arc in PG(w ? 2, q).     

Normal connections induced by a framed hypersurface in the conformal space

We find two normal connections induced by the normal framing of a hypersurface V _{n ? 1} in the conformal space C _n , and establish relationship between these connections and a Weyl connection which is also induced by the normal framing of V _{n ? 1}. We study two normal connections induced by a complete framing of a hypersurface V _{n ? 1} in C _n . We establish relationship between geometries of a framed hypersurface V _{n ? 1} of the conformal space C _n and a quadratic hyperband of the projective space P _{n + 1} associated with V _{n ? 1}.     

Solving Equations of Free Vibration for a Cylindrical Shell Rotating on Rollers by the Fourier Method

The small free vibrations of an infinite circular cylindrical shell rotating about its axis at a constant angular velocity are considered. The shell is supported on n absolutely rigid cylindrical rollers equispaced on its circle. The roller-supported shell is a model of an ore benefication centrifugal concentrator with a floating bed. The set of linear differential equations of vibrations is sought in the form of a truncated Fourier series containing N terms along the circumferential coordinate. A system of 2N–n linear homogeneous algebraic equations with 2N–n unknowns is derived for the approximate estimation of vibration frequencies and mode shapes. The frequencies ω _k , k = 1, 2, …, 2N–n, are positive roots of the (2N–n)th-order algebraic equation D(ω²) = 0, where D is the determinant of this set. It is shown that the system of 2N–n equations is equivalent to several independent systems with a smaller number of unknowns. As a consequence, the (2N–n)th-order determinant D can be written as a product of lower-order determinants. In particular, the frequencies at N = n are the roots of algebraic equations of an order is lower than 2 and can be found in an explicit form. Some frequency estimation algorithms have been developed for the case of N > n. When N increases, the number of found frequencies also grows, and the frequencies determined at N = n are refined. However, in most cases, the vibration frequencies can not be found for N > n in an explicit form.     

Unique solvability of the stationary Fokker-Planck equation in a class of positive functions

We study the stationary Focker-Planck equation Δu ? div(u f) = 0 with a given vector field f of the class C ₀ ^∞ (R ⁿ ) on the basis of a fixed point principle that generalizes the contraction mapping method. Next, we introduce a parameter in the equation and prove the unique solvability of the equation Δu ? div(uγ f) = 0 with the parameter in the class of positive slowly increasing functions. We reveal the analytic dependence of the positive solution u on the parameter γ. Pointwise estimates for positive solutions are proved.     

Modified Kantorovich theorem and asymptotic approximations of solutions to singularly perturbed systems of ordinary differential equations

The functional equation f(x,ε) = 0 containing a small parameter ε and admitting regular and singular degeneracy as ε → 0 is considered. By the methods of small parameter, a function x _n ⁰(ε) satisfying this equation within a residual error of O(ε ⁿ⁺¹) is found. A modified Newton’s sequence starting from the element x _n ⁰(ε) is constructed. The existence of the limit of Newton’s sequence is based on the NK theorem proven in this work (a new variant of the proof of the Kantorovich theorem substantiating the convergence of Newton’s iterative sequence). The deviation of the limit of Newton’s sequence from the initial approximation x _n ⁰(ε) has the order of O(ε ⁿ⁺¹), which proves the asymptotic character of the approximation x _n ⁰(ε). The method proposed is implemented in constructing an asymptotic approximation of a system of ordinary differential equations on a finite or infinite time interval with a small parameter multiplying the derivatives, but it can be applied to a wider class of functional equations with a small parameters.     

Solution of a Ball–Murat problem

A necessary and sufficient condition for the W ^{1, p} -quasi-convexity of integrands to imply the lower semicontinuity of the corresponding integral functionals with respect to the weak convergence of sequences in W ^{1, p} is obtained. It is shown that the absence of the Lavrent’ev phenomenon in minimization problems with linear boundary data is sufficient, under a minor technical assumption, for the lower semicontinuity of integral functionals with quasi-convex integrands.