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.     

Invariance of the generalized oscillator under a linear transformation of the related system of orthogonal polynomials

We consider the families of polynomials P = { P _n (x)} _n=0 ^∞ and Q = { Q _n (x)} _n=0 ^∞ orthogonal on the real line with respect to the respective probability measures μ and ν. We assume that { Q _n (x)} _n=0 ^∞ and {P _n (x)} _n=0 ^∞ are connected by linear relations. In the case k = 2, we describe all pairs (P,Q) for which the algebras A _P and A _Q of generalized oscillators generated by { Qn(x)} _n=0 ^∞ and { Pn(x)} _n=0 ^∞ coincide. We construct generalized oscillators corresponding to pairs (P,Q) for arbitrary k ≥ 1.     

Krein Extension of an Even-Order Differential Operator

We describe the Krein extension of the minimal operator associated with the expression A:= (?1) ⁿ d²ⁿ/dx²ⁿ on the interval [a, b] in terms of boundary conditions. We also describe all nonnegative extensions of the operator A and extensions with finitely many negative squares.     

The Erdös-Kac theorem for additive arithmetical semigroups

We show that the Erdös-Kac theorem for additive arithmetical semigroups can be proved under the condition that the counting function of elements has the asymptotics G(n) = q ⁿ (A + O(1/(lnn)^k) as n → ∞ with A > 0, q > 1, and arbitrary k ∈ ? and that P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This improves a result of Zhang.     

Nonparametric mean estimation of percentage points and density function values

Let us consider a sample of sizen from a statistical population with probability density function f(x) and 100p per cent point θ_p. The functionf (x) is assumed to be of an analytic nature. This paper presents some methods for approximate nonparametric expected value estimation of θ_p and 1/f(θ _p ). These results are applicable for anyp value which is not too near 0 or 1 and alln values which are not too small. A nonparametric estimate whose expected value differs from θ _p by terms of ordern ^?7/1 can be obtained. For l/f(θ _p ), an estimate whose expected value is accurate to terms of ordern ^?3can be obtained. The estimates developed consist of linear functions of specified order statistics of the sample. The order statistics used are sample percentage points with percentage values which are near 100p. Letm be the number of order statistics appearing in an estimate (m is at most 7). Then the coefficients for the linear estimation function are obtained by solving a specified set of m linear equations inm unknowns. All the estimates presented are consistent.     

On the 1/3–2/3 Conjecture

Let (P, ≤) be a finite poset (partially ordered set), where P has cardinality n. Consider linear extensions of P as permutations x₁x₂?x_n in one-line notation. For distinct elements x, y ∈ P, we define ?(x ? y) to be the proportion of linear extensions of P in which x comes before y. For \(0\leq \alpha \leq \frac {1}{2}\), we say (x, y) is an α-balanced pair if α ≤ ?(x ? y) ≤?1 ? α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2. We also consider various posets which satisfy the stronger condition of having a 1/2-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length 2. Various questions for future research are posed.     

On a space of smooth functions on a convex unbounded set in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> admitting holomorphic extension in ℂ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

For some given logarithmically convex sequence M of positive numbers we construct a subspace of the space of rapidly decreasing infinitely differentiable functions on an unbounded closed convex set in ? ⁿ . Due to the conditions on M each function of this space admits a holomorphic extension in ? ⁿ . In the current article, the space of holomorphic extensions is considered and Paley-Wiener type theorems are established. To prove these theorems, some auxiliary results on extensions of holomorphic functions satisfying some weighted L ²-bounds in a domain of holomorphy in ? ⁿ are obtained with the aid of L. Hörmander’s method of L ²-bounds for the \(\bar \partial\) operator. Also, some new facts on the Fourier-Laplace transform of tempered distributions complementing some well-known results of V.S. Vladimirov are employed.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

Upper bound for the length of functions over a finite field in the class of pseudopolynomials

An exclusive-OR sum of pseudoproducts (ESPP), or a pseudopolynomial over a finite field is a sum of products of linear functions. The length of an ESPP is defined as the number of its pairwise distinct summands. The length of a function f over this field in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L _k ^ESPP (n) on the set of functions over a finite field of k elements in the class of ESPPs is considered; it is defined as the maximum length of a function of n variables over this field in the class of ESPPs. It is proved that L _k ^ESPP (n) = O(k ⁿ /n ²).     

A probabilistic approach to polynomial inequalities

We define a probability measure on the space of polynomials over ? ⁿ in order to address questions regarding the attainment of the norm at given points and the validity of polynomial inequalities.Using this measure, we prove that for all degrees k ≥ 3, the probability that a k-homogeneous polynomial attains a local extremum at a vertex of the unit ball of ? ₁ ⁿ tends to one as the dimension n increases. We also give bounds for the probability of some general polynomial inequalities.     

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.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Linear homotopy method for computing generalized tensor eigenpairs

Let m,m′, n be positive integers such that m ≠ m′. Let A be an mth order n-dimensional tensor, and let ? be an m′th order n-dimensional tensor. λ ∈ ? is called a ?-eigenvalue of A if A x^m?1 = λ?x^m′?1 and ?xm′= 1 for some x ∈ ?ⁿ\{0}. In this paper, we propose a linear homotopy method for solving this eigenproblem. We prove that the method finds all isolated ?-eigenpairs. Moreover, it is easy to implement. Numerical results are provided to show the efficiency of the proposed method.     

Augmentation quotients for burnside rings of generalized dihedral groups

Let H be a finite abelian group of odd order, D be its generalized dihedral group, i.e., the semidirect product of C₂ acting on H by inverting elements, where C₂ is the cyclic group of order two. Let Ω (D) be the Burnside ring of D, Δ(D) be the augmentation ideal of Ω (D). Denote by Δⁿ(D) and Q_n(D) the nth power of Δ(D) and the nth consecutive quotient group Δⁿ(D)/Δⁿ⁺¹(D), respectively. This paper provides an explicit Z-basis for Δⁿ(D) and determines the isomorphism class of Q_n(D) for each positive integer n.     

A Note on Average-Case Sorting

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.     

On the measurable chromatic number of a space of dimension n ≤ 24

This paper is devoted to the classical problem of finding the measurable chromatic number of n-dimensional Euclidean space, i.e., the value χ _m (? ⁿ ) equal to the least possible number of Lebesgue measurable sets that do not contain pairs of points at a distance of 1 and cover the whole space. Assuming that a certain hypothesis is true, we significantly improve the lower bounds for χ _m (? ⁿ ).     

On necessary and sufficient conditions for the self-normalized central limit theorem

Let X₁, X₂, … be a sequence of independent random variables and S_n = Σ _i=1 ⁿ X_i and V _n ² = Σ _i=1 ⁿ X _i ² . When the elements of the sequence are i.i.d., it is known that the self-normalized sum S_n=V_n converges to a standard normal distribution if and only if max_1?i?n|X_i|/V_n→0 in probability and the mean of X₁ is zero. In this paper, sufficient conditions for the self-normalized central limit theorem are obtained for general independent random variables. It is also shown that if max_1?i?n|X_i|/V_n→0 in probability, then these sufficient conditions are necessary.     

Arithmetic Progressions in Linear Combinations of <Emphasis Type="Italic">S</Emphasis>-Units

M. Pohst asked the following question: is it true that every prime can be written in the form 2^u ± 3^v with some non-negative integers u, v? We put the problem into a general framework, and prove that the length of any arithmetic progression in t-term linear combinations of elements from a multiplicative group of rank r (e.g. of S-units) is bounded in terms of r, t, n, where n is the number of the coefficient t-tuples of the linear combinations. Combining this result with a recent theorem of Green and Tao on arithmetic progressions of primes, we give a negative answer to the problem of M. Pohst.     

Equalities on the number of conjugacy classes of the Sylow p-subgroups of GL(n,q)

We denote by Gn the group of the upper unitriangular matrices over F_q, the finite field with q = p^t elements, and r(G_n) the number of conjugacy classes of G_n. In this paper, we obtain the value of r(G_n) modulo (q² -1)(q -1). We prove the following equalities