Q 2-free Families in the Boolean Lattice

For a family F{{\cal F}} of subsets of [n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of [n]. Let Q ₂ be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q ₂) ≤ 2.283261N + o(N), where N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q ₂-free family of subsets of [n] having at most three different sizes has at most 2.20711N members.     

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

On the lemniscate components containing no critical points of a polynomial except for its zeros

Let P be a complex polynomial of degree n and let E be a connected component of the set {z : |P(z)| ≤ 1} containing no critical points of P different from its zeros. We prove the inequality |(z − a)P′(z)/P(z)| ≤ n for all z ∈ E \ {a}, where a is the zero of the polynomial P lying in E. Equality is attained for P(z) = cz ⁿ and any z, c ≠ 0. Bibliography: 4 titles.     

A Generalized Radon Transform on the Plane

A new generalized Radon transform R _α, β on the plane for functions even in each variable is defined which has natural connections with the bivariate Hankel transform, the generalized biaxially symmetric potential operator Δ _α, β , and the Jacobi polynomials P_k^(b, a)(t)P_{k}^{(\beta,\,\alpha)}(t). The transform R _α, β and its dual R_a, b^*R_{\alpha,\,\beta}^{\ast} are studied in a systematic way, and in particular, the generalized Fuglede formula and some inversion formulas for R _α, β for functions in L_a, b^p(\mathbbR²₊)L_{\alpha,\,\beta}^{p}(\mathbb{R}^{2}_{+}) are obtained in terms of the bivariate Hankel–Riesz potential. Moreover, the transform R _α, β is used to represent the solutions of the partial differential equations Lu:=?_j=1^ma_jD_a, b^ju=fLu:=\sum_{j=1}^{m}a_{j}\Delta_{\alpha,\,\beta}^{j}u=f with constant coefficients a _j and the Cauchy problem for the generalized wave equation associated with the operator Δ _α, β . Another application is that, by an invariant property of R _α, β , a new product formula for the Jacobi polynomials of the type P_k^(b, a)(s)C_2k^a+b+1(t)=còòP_k^(b, a)P_{k}^{(\beta,\,\alpha)}(s)C_{2k}^{\alpha+\beta+1}(t)=c\int\!\!\int P_{k}^{(\beta,\,\alpha)} is obtained.     

Extremes of independent Gaussian processes

For every n ∈ ℕ, let X _1n ,..., X _nn be independent copies of a zero-mean Gaussian process X _n  = {X _n (t), t ∈ T}. We describe all processes which can be obtained as limits, as n→ ∞, of the process a _n (M _n  − b _n ), where M _n (t) =  max _{i = 1,...,n} X _in (t), and a _n , b _n are normalizing constants. We also provide an analogous characterization for the limits of the process a _n L _n , where L _n (t) =  min _{i = 1,...,n} |X _in (t)|.     

The primes contain arbitrarily long polynomial progressions

We establish the existence of infinitely many polynomial progressions in the primes; more precisely, given any integer-valued polynomials P ₁, …, P _k  ∈ Z[m] in one unknown m with P ₁(0) = … = P _k (0) = 0, and given any ε > 0, we show that there are infinitely many integers x and m, with 1 \leqslant m \leqslant x^e1 \leqslant m \leqslant x^\varepsilon, such that x + P ₁(m), …, x + P _k (m) are simultaneously prime. The arguments are based on those in [18], which treated the linear case P _j  = (j − 1)m and ε = 1; the main new features are a localization of the shift parameters (and the attendant Gowers norm objects) to both coarse and fine scales, the use of PET induction to linearize the polynomial averaging, and some elementary estimates for the number of points over finite fields in certain algebraic varieties.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Estimation of a distribution function by an indirect sample

The problem of estimation of a distribution function is considered in the case where the observer has access only to a part of the indicator random values. Some basic asymptotic properties of the constructed estimates are studied. The limit theorems are proved for continuous functionals related to the estimation of [^(F)]_n(x) {\hat{F}_n}(x) in the space C[a, 1 - a], 0 < a < 1/2.     

Locally Closed Semirings

 We call a semiring S locally closed if for all a ∈ S there is some integer k such that 1 + a + ⋯ + a ^k  =1 + a + ⋯ + a ^k + 1 . In any locally closed semiring we may define a star operation a ↦ a ^*, where a ^* is the above finite sum. We prove that when S is locally closed and commutative, then S is an iteration semiring.     

Random Partial Orders Defined by Angular Domains

The d-dimensional random partial order is the intersection of d independently and uniformly chosen (with replacement) linear orders on the set [n] = {1, 2, . . . , n}. This is equivalent to picking n points uniformly at random in the d-dimensional unit cube Q_d=[0,1]^dQ_d=[0,1]^d with the coordinate-wise ordering. If d = 2, then this can be rephrased by declaring that for any pair P ₁, P ₂ ∈ Q ₂ we have P ₁ ≺ P ₂ if and only if P ₂ lies in the positive upper quadrant defined by the two axis-parallel lines crossing at P ₁. In this paper we study the random partial order with parameter α (0 ≤ α ≤ π) which is generated by picking n points uniformly at random from Q ₂ equipped with the same partial order as above but with the quadrant replaced by an angular domain of angle α.     

On a Sharper Lower Bound for a Percentile of a Student’s <Emphasis Type="Italic">t</Emphasis> Distribution with an Application

In this communication, we first compare z _α and t _ν,α , the upper 100α% points of a standard normal and a Student’s t _ν distributions respectively. We begin with a proof of a well-known result, namely, for every fixed 0 < a < \frac120<\alpha <\frac{1}{2} and the degree of freedom ν, one has t _ν,α  > z _α . Next, Theorem 3.1 provides a new and explicit expression b _ν ( > 1) such that for every fixed 0 < a < \frac120<\alpha < \frac{1}{2} and ν, we can conclude t _ν,α  > b _ν z _α . This is clearly a significant improvement over the result that is customarily quoted in nearly every textbook and elsewhere. A proof of Theorem 3.1 is surprisingly simple and pretty. We also extend Theorem 3.1 in the case of a non-central Student’s t distribution (Section 3.3). In the context of Stein’s (Ann Math Stat 16:243–258, 1945; Econometrica 17:77–78, 1949) 100(1 − α)% fixed-width confidence intervals for the mean of a normal distribution having an unknown variance, we have examined the oversampling rate on an average for a variety of choices of m, the pilot sample size. We ran simulations to investigate this issue. We have found that the oversampling rates are approximated well by t_n,a/2²z_a/2^-2t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2} for small and moderate values of m( ≤ 50) all across Table 2 where ν = m − 1. However, when m is chosen large (≥ 100), we find from Table 3 that the oversampling rates are not approximated by t_n,a/2²z_a/2^-2t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2} very well anymore in some cases, and in those cases the oversampling rates either exceed the new lower bound of t_n,a/2²z_a/2^-2,t_{\nu ,\alpha /2}^{2}z_{\alpha /2}^{-2}, namely b_n²,b_{\nu }^{2}, or comes incredibly close to b_n²b_{\nu }^{2} where ν = m − 1. That is, the new lower bound for a percentile of a Student’s t distribution may play an important role in order to come up with diagnostics in our understanding of simulated output under Stein’s fixed-width confidence interval method.     

Uniform rates of approximation by short asymptotic expansions in the CLT for quadratic forms

Let X, X ₁, X ₂,… be i.i.d. \mathbbR^d {\mathbb{R}^d} -valued real random vectors. Assume that E X = 0 and that X has a nondegenerate distribution. Let G be a mean zero Gaussian random vector with the same covariance operator as that of X. We study the distributions of nondegenerate quadratic forms \mathbbQ[ S_N ] \mathbb{Q}\left[ {{S_N}} \right] of the normalized sums S _N  = N ^−1/2 (X ₁ + ⋯ + X _N ) and show that, without any additional conditions,

Dense inverse subsemigroups of a topological inverse semigroup

In this paper we study dense inverse subsemigroups of topological inverse semigroups. We construct a topological inverse semigroup from a semilattice. Finally, we give two examples of the closure of B _{( −∞, ∞ )}¹, a topological inverse semigroup obtained by starting with the real numbers as a semilattice with the operation a ∨ b=sup{a,b}. The author would like to thank to the referee for useful suggestions.     

Locally Closed Semirings

 We call a semiring S locally closed if for all a ∈ S there is some integer k such that 1 + a + ⋯ + a ^k  =1 + a + ⋯ + a ^k + 1 . In any locally closed semiring we may define a star operation a ↦ a ^*, where a ^* is the above finite sum. We prove that when S is locally closed and commutative, then S is an iteration semiring. Partially supported by grant no. T30511 from the National Foundation of Hungary for Scientific Research and the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Partially supported by the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Received March 16, 2001     

Strict Betweennesses Induced by Posets as well as by Graphs

For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V ³ such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let B_s(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V ³ such that y is an internal vertex on an induced path in G between x and z. The ternary relations B_s(P){\cal B}_s(P) and B_s(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation B_s(P)=B_s(G){\cal B}_s(P)={\cal B}_s(G).     

The Lambert W-functions and some of their integrals: a case study of high-precision computation

The real-valued Lambert W-functions considered here are w ₀(y) and w _− 1(y), solutions of we ^w  = y, − 1/e < y < 0, with values respectively in ( − 1,0) and ( − ∞ , − 1). A study is made of the numerical evaluation to high precision of these functions and of the integrals ò₁^￥ [-w₀(-xe^-x)]^a x^-bx\int_1^\infty [-w_0(-xe^{-x})]^\alpha x^{-\beta}\d x, α > 0, β ∈ ℝ, and ò₀¹ [-w_-1(-x e^-x)]^a x^-bx\int_0^1 [-w_{-1}(-x e^{-x})]^\alpha x^{-\beta}\d x, α > − 1, β < 1. For the latter we use known integral representations and their evaluation by nonstandard Gaussian quadrature, if α ≠ β, and explicit formulae involving the trigamma function, if α = β.     

Asymptotics of random sums of negatively dependent random variables in the presence of dominatedly varying tails

Let X ₁ , X ₂ , . . . be a sequence of negatively dependent and identically distributed random variables, and let N be a counting random variable independent of X _i ’s. In this paper, we study the asymptotics for the tail probability of the random sum S_N = ?_{k = 1}^N X_k {S_N} = \sum\nolimits_{k = 1}^N {{X_k}} in the presence of heavy tails. We consider the following three cases: (i) P(N > x) = o(P(X ₁  > x)), and the distribution function (d.f.) of X ₁ is dominatedly varying; (ii) P(X ₁  > x) = o(P(N > x)), and the d.f. of N is dominatedly varying; (iii) the tails of X ₁ and N are asymptotically comparable and dominatedly varying.     

On the Order Dimension of Outerplanar Maps

Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset P _M of a planar map M is at most four. In this paper we investigate cases where dim(P _M ) ≤ 3 and also where dim(Q _M ) ≤ 3; here Q _M denotes the vertex-face poset of M. We show:

Weighted Polynomials on Discrete Sets

 For a real interval I of positive length, we prove a necessary and sufficient condition which ensures that the continuous L _p (0 < p ⩽ ∞) norm of a weighted polynomial, P _n w ⁿ , deg P _n  ⩽ n, n ⩾ 1 is in an nth root sense, controlled by its corresponding discrete H?lder norm on a very general class of discrete subsets of I. As a by product of our main result, we establish inequalities and theorems dealing with zero distribution, zero location and sup and L _p infinite–finite range inequalities.