New cases of Reay’s conjecture on partitions of points into simplices with -dimensional intersection

Reay’s conjecture asserts that every set of (m−1)(d+1)+k+1 points in general position in (with 0≤k≤d) has a partition X₁,X₂,…,X_m such that is at least k-dimensional. We prove this conjecture in several cases: when m≤8 (for arbitrary d and k), when d=6,d=7 and d=8 (for arbitrary m and k), and when k=1 and d≤24 (for arbitrary m).     

Periodic Schur functions and slit discs

A simply connected domain is called a slit disc if minus a finite number of closed radial slits not reaching the origin. A slit disc is called rational (rationally placed) if the lengths of all its circular arcs between neighboring slits (the arguments of the slits) are rational multiples of 2π. The conformal mapping of onto , (0)=0, ^′(0)>0, extends to a continuous function on mapping it onto . A finite union E of closed non-intersecting arcs e_k on is called rational if for every k, ν_E(e_k) being the harmonic measures of e_k at ∞ for the domain . A compact E is rational if and only if there is a rational slit disc such that . A compact E essentially supports a measure with periodic Verblunsky parameters if and only if for a rationally placed . For any tuple (α₁,…,α_g+1) of positive numbers with ∑_kα_k=1 there is a finite family of closed non-intersecting arcs e_k on such that ν_E(e_k)=α_k. For any set and any >0 there is a rationally placed compact such that the Lebesgue measure |EE^*| of the symmetric difference EE^* is smaller than .     

Some extensions of a property of linear representation functions

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers. Let k≥2 be a fixed integer and for , let R_k(A,n) be the number of solutions of a_i1++a_ik=n,a_i1,…,a_ikA, and let and denote the number of solutions with the additional restrictions a_i1<<a_ik, and a_i1≤≤a_ik respectively. Recently, Horváth proved that if d>0 is an integer, then there does not exist n₀ such that for n>n₀. In this paper, we obtain the analogous results for R_k(A,n), and .     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.     

Orthogonal Laurent polynomials on the unit circle and snake-shaped matrix factorizations

Let there be given a probability measure μ on the unit circle of the complex plane and consider the inner product induced by μ. In this paper we consider the problem of orthogonalizing a sequence of monomials {z^r_k}_k, for a certain order of the , by means of the Gram–Schmidt orthogonalization process. This leads to a sequence of orthonormal Laurent polynomials {ψ_k}_k. We show that the matrix representation with respect to {ψ_k}_k of the operator of multiplication by z is an infinite unitary or isometric matrix allowing a ‘snake-shaped’ matrix factorization. Here the ‘snake shape’ of the factorization is to be understood in terms of its graphical representation via sequences of little line segments, following an earlier work of S. Delvaux and M. Van Barel. We show that the shape of the snake is determined by the order in which the monomials {z^r_k}_k are orthogonalized, while the ‘segments’ of the snake are canonically determined in terms of the Schur parameters for μ. Isometric Hessenberg matrices and unitary five-diagonal matrices (CMV matrices) follow as a special case of the presented formalism.     

Precise asymptotics in the self-normalized law of the iterated logarithm

Let X,X₁,X₂,… be i.i.d. nondegenerate random variables with zero means, and . We investigate the precise asymptotics in the law of the iterated logarithm for self-normalized sums, S_n/V_n, also for the maximum of self-normalized sums, max_1kn|S_k|/V_n, when X belongs to the domain of attraction of the normal law.     

An Erdo&#x030B;s–Ko–Rado Theorem for Direct Products

Letn_i, k_ibe positive integers,i=1, ..., d,satisfyingn_i≥2k_i.LetX₁, ..., X_dbe pairwise disjoint sets with |X_i| =n_i.Letbe the family of those (k₁+···+k_d)-element sets which have exactlyk_ielements inX_i, i=1,..., d.It is shown that if⊂is an intersecting family then ||/||≤max_ik_i/n_i,and this is best possible. The proof is algebraic, although in thed=2 case a combinatorial argument is presented as well.     

Constrained versions of Sauer’s lemma

Let [n]={1,…,n}. For a function h:[n]→{0,1}, x[n] and y{0,1} define by the width ω_h(x,y) of h at x the largest nonnegative integer a such that h(z)=y on x−a≤z≤x+a. We consider finite VC-dimension classes of functions h constrained to have a width ω_h(x_i,y_i) which is larger than N for all points in a sample or a width no larger than N over the whole domain [n]. Extending Sauer’s lemma, a tight upper bound with closed-form estimates is obtained on the cardinality of several such classes.     

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

We consider the bounded integer knapsack problem (BKP) , subject to: , and x_j{0,1,…,m_j},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=max_j=1,…,nw_j. The respective complexity of the unbounded case with m_j=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.     

The statistical distribution of the zeros of random paraorthogonal polynomials on the unit circle

The orthogonal polynomials on the unit circle are defined by the recurrence relation

where for any k0. If we consider n complex numbers and , we can use the previous recurrence relation to define the monic polynomials Φ₀,Φ₁,…,Φ_n. The polynomial Φ_n(z)=Φ_n(z;α₀,…,α_n-2,α_n-1) obtained in this way is called the paraorthogonal polynomial associated to the coefficients α₀,α₁,…,α_n-1.We take α₀,α₁,…,α_n-2 i.i.d. random variables distributed uniformly in a disk of radius r<1 and α_n-1 another random variable independent of the previous ones and distributed uniformly on the unit circle. For any n we will consider the random paraorthogonal polynomial Φ_n(z)=Φ_n(z;α₀,…,α_n-2,α_n-1). The zeros of Φ_n are n random points on the unit circle.We prove that for any the distribution of the zeros of Φ_n in intervals of size near e^iθ is the same as the distribution of n independent random points uniformly distributed on the unit circle (i.e., Poisson). This means that, for large n, there is no local correlation between the zeros of the considered random paraorthogonal polynomials.     

Intersective polynomials and the polynomial Szemerédi theorem

Let be a family of polynomials such that , i=1,…,r. We say that the family P has the PSZ property if for any set with there exist infinitely many such that E contains a polynomial progression of the form {a,a+p₁(n),…,a+p_r(n)}. We prove that a polynomial family P={p₁,…,p_r} has the PSZ property if and only if the polynomials p₁,…,p_r are jointly intersective, meaning that for any there exists such that the integers p₁(n),…,p_r(n) are all divisible by k. To obtain this result we give a new ergodic proof of the polynomial Szemerédi theorem, based on the fact that the key to the phenomenon of polynomial multiple recurrence lies with the dynamical systems defined by translations on nilmanifolds. We also obtain, as a corollary, the following generalization of the polynomial van der Waerden theorem: If are jointly intersective integral polynomials, then for any finite partition of , there exist i{1,…,k} and a,nE_i such that {a,a+p₁(n),…,a+p_r(n)}E_i.     

Algebraic series and valuation rings over nonclosed fields

Suppose that k is an arbitrary field. Let k[[x₁,…,x_n]] be the ring of formal power series in n variables with coefficients in k. Let be the algebraic closure of k and . We give a simple necessary and sufficient condition for σ to be algebraic over the quotient field of k[[x₁,…,x_n]]. We also characterize valuation rings V dominating an excellent Noetherian local domain R of dimension 2, and such that the rank increases after passing to the completion of a birational extension of R. This is a generalization of the characterization given by M. Spivakovsky [Valuations in function fields of surfaces, Amer. J. Math. 112 (1990) 107–156] in the case when the residue field of R is algebraically closed.     

Properties of multilevel block -circulants

In a previous paper we characterized unilevel block α-circulants , , 0mn-1, in terms of the discrete Fourier transform of , defined by . We showed that most theoretical and computational problems concerning A can be conveniently studied in terms of corresponding problems concerning the Fourier coefficients F₀,F₁,…,F_n-1 individually. In this paper we show that analogous results hold for (k+1)-level matrices, where the first k levels have block circulant structure and the entries at the (k+1)-st level are unstructured rectangular matrices.     

Global stability of a difference equation with maximum

We prove that every positive solution to the difference equation

where , i=1,…,k, converges to the following quantity , confirming a quite recent conjecture of interest. We also prove another result on global convergence which concerns some cases when not all α_i,i=1,…,k belong to the interval (0, 1).     

Relative asymptotic of multiple orthogonal polynomials for Nikishin systems

We prove the relative asymptotic behavior for the ratio of two sequences of multiple orthogonal polynomials with respect to the Nikishin systems of measures. The first Nikishin system is such that for each k, σ_k has a constant sign on its compact support consisting of an interval , on which almost everywhere, and a discrete set without accumulation points in . If denotes the smallest interval containing , we assume that Δ_k∩Δ_k+1=0/, k=1,…,m−1. The second Nikishin system is a perturbation of the first by means of rational functions r_k, k=1,…,m, whose zeros and poles lie in .     

On value sets of polynomials over a field

Let F be any field. Let p(F) be the characteristic of F if F is not of characteristic zero, and let p(F)=+∞ otherwise. Let A₁,…,A_n be finite nonempty subsets of F, and let

with k{1,2,3,…}, a₁,…,a_nF{0} and degg<k. We show that

When kn and |A_i|i for i=1,…,n, we also have

consequently, if nk then for any finite subset A of F we have

In the case n>k, we propose a further conjecture which extends the Erdős–Heilbronn conjecture in a new direction.     

VC dimension and inner product space induced by Bayesian networks

Bayesian networks are graphical tools used to represent a high-dimensional probability distribution. They are used frequently in machine learning and many applications such as medical science. This paper studies whether the concept classes induced by a Bayesian network can be embedded into a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. For full Bayesian networks and almost full Bayesian networks with n variables, we show that VC dimension and the minimum dimension of the inner product space induced by them are 2ⁿ-1. Also, for each Bayesian network we show that if the network constructed from by removing X_n satisfies either (i) is a full Bayesian network with n-1 variables, i is the number of parents of X_n, and i<n-1 or (ii) is an almost full Bayesian network, the set of all parents of X_n PA_n={X₁,X₂,X_n3,…,X_ni} and 2i<n-1. Our results in the paper are useful in evaluating the VC dimension and the minimum dimension of the inner product space of concept classes induced by other Bayesian networks.     

The energy of unitary cayley graphs

A graph G of order n is called hyperenergetic if E(G)>2n-2, where E(G) denotes the energy of G. The unitary Cayley graph X_n has vertex set Z_n={0,1,2,…,n-1} and vertices a and b are adjacent, if gcd(a-b,n)=1. These graphs have integral spectrum and play an important role in modeling quantum spin networks supporting the perfect state transfer. We show that the unitary Cayley graph X_n is hyperenergetic if and only if n has at least two prime factors greater than 2 or at least three distinct prime factors. In addition, we calculate the energy of the complement of unitary Cayley graph and prove that is hyperenergetic if and only if n has at least two distinct prime factors and n≠2p, where p is a prime number. By extending this approach, for every fixed , we construct families of k hyperenergetic non-cospectral integral circulant n-vertex graphs with equal energy.     

Positive periodic solutions of periodic neutral Lotka–Volterra system with state dependent delays

By using a fixed point theorem of strict-set-contraction, some new criteria are established for the existence of positive periodic solutions of the following periodic neutral Lotka–Volterra system with state dependent delays

where (i,j=1,2,…,n) are ω-periodic functions and (i=1,2,…,n) are ω-periodic functions with respect to their first arguments, respectively.