A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x)–h _L (y)|≤k, where h _L (x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3. We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal of specific comparisons. The first and second authors were supported during this research by National Science Foundation VIGRE grant DMS-0135290.     

When linear and weak discrepancy are equal

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable, then |h_L(x)−h_L(y)|≤k, whereas the weak discrepancy is the least k such that there is a weak extension W of P such that if x and y are incomparable, then |h_W(x)−h_W(y)|≤k. This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is -complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders.     

The total linear discrepancy of an ordered set

In this paper we introduce the notion of the total linear discrepancy of a poset as a way of measuring the fairness of linear extensions. If L is a linear extension of a poset P, and x,y is an incomparable pair in P, the height difference between x and y in L is |L(x)−L(y)|. The total linear discrepancy of P in L is the sum over all incomparable pairs of these height differences. The total linear discrepancy of P is the minimum of this sum taken over all linear extensions L of P. While the problem of computing the (ordinary) linear discrepancy of a poset is NP-complete, the total linear discrepancy can be computed in polynomial time. Indeed, in this paper, we characterize those linear extensions that are optimal for total linear discrepancy. The characterization provides an easy way to count the number of optimal linear extensions.     

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.     

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

Integral representation of even positive-definite functions of two variables

We obtain an integral representation of even functions of two variables for which the kernel [k ₁(x + y) + k ₂(x − y)], x, y ∈ R ², is positive definite.     

Orders on Multisets and Discrete Cones

We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of independence of equal submultisets (IES) introduced by Sertel and Slinko (Ranking committees, words or multisets. Nota di Laboro 50.2002. Center of Operation Research and Economics. The Fundazione Eni Enrico Mattei, Milan, 2002, Econ. Theory 30(2):265–287, 2007). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (J. Math. Psychol., 40:64–77, 1996) and Conder and Slinko (J. Math. Psychol., 48(6):425–431, 2004), we define functions f(n,k) and g(n,k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n,k) = n − 1 whenever n ≥ 3 and (n, k) ≠ (5, 2). In the exceptional case, g(5,2) = 3. We also prove that g(n,k) ≤ f(n,k) ≤ n and establish that for small n and k the functions g(n,k) and f(n,k) coincide.      

A generalized mixed type of quartic–cubic–quadratic–additive functional equations

We determine the general solution of the functional equation f(x + ky) + f(x-ky) = g(x + y) + g(x-y) + h(x) + h(y) for fixed integers with k ≠ 0; ±1 without assuming any regularity conditions for the unknown functions f, g, h, and0020[(h)\tilde] \tilde{h} . The method used for solving these functional equations is elementary but it exploits an important result due to Hosszú. The solution of this functional equation can also be obtained in groups of certain type by using two important results due to Székelyhidi.     

Integral representation of even positive-definite functions of one variable

We obtain an integral representation of even positive-definite functions of one variable for which the kernel [k ₁(x + y) + k ₂ (x − y)] is positive definite.     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

Minimax risk over quadratically convex sets

We consider the problem of estimating a vector θ = (θ₁, θ₂,…) ∈ Θ ⊂ l ₂ from observations y _i = θ _i + σ _i x _i , i = 1, 2,…, where the random values x _i are N(0, 1), independent, and identically distributed, the parametric set Θ is compact, orthosymmetric, convex, and quadratically convex. We show that in that case, the minimax risk is not very different from sup?_L( P) \sup {\Re_L}\left( \Pi \right) , where ?_L( P) {\Re_L}\left( \Pi \right) is the minimax linear risk in the same problem with parametric set Π, and sup is taken over all the hyperrectangles Π ⊂ Θ. Donoho, Liu, and McGibbon (1990) have obtained this result for the case of equal σ _i , i = 1, 2,…. Bibliography: 4 titles.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Construction of positive definite cubature formulae and approximation of functions via Voronoi tessellations

Let Ω ⊂ ℝ ^d be a compact convex set of positive measure. In a recent paper, we established a definiteness theory for cubature formulae of order two on Ω. Here we study extremal properties of those positive definite formulae that can be generated by a centroidal Voronoi tessellation of Ω. In this connection we come across a class of operators of the form L_n[f](x): = ?_i=1ⁿ f_i(x)(f(y_i) + á?f(y_i), x-y_i?)L_n[f](\boldsymbol{x}):= \sum_{i=1}^n \phi_i(\boldsymbol{x})(f(\boldsymbol{y}_i) + \langle\nabla f(\boldsymbol{y}_i), \boldsymbol{x}-\boldsymbol{y}_i\rangle), where y₁,..., y_n\boldsymbol{y}_1,\dots, \boldsymbol{y}_n are distinct points in Ω and {ϕ ₁, ..., ϕ _n } is a partition of unity on Ω. We present best possible pointwise error estimates and describe operators L _n with a smallest constant in an L ^p error estimate for 1 ≤ p < ∞ . For a generalization, we introduce a new type of Voronoi tessellation in terms of a twice continuously differentiable and strictly convex function f. It allows us to describe a best operator L _n for approximating f by L _n [f] with respect to the L ^p norm.     

Topology of Hom complexes and test graphs for bounding chromatic number

The Hom complex of homomorphisms between two graphs was originally introduced to provide topological lower bounds on the chromatic number. In this paper we introduce new methods for understanding the topology of Hom complexes, mostly in the context of Γ-actions on graphs and posets (for some group Γ). We view the Hom(T, ⊙) and Hom(⊙, G) complexes as functors from graphs to posets, and introduce a functor (⊙)¹ from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of Hom complexes in terms of spaces of equivariant poset maps and Γ-twisted products of spaces. When P:= F(X) is the face poset of a simplicial complex X, this provides a useful way to control the topology of Hom complexes. These constructions generalize those of the second author from [17] as well as the calculation of the homotopy groups of Hom complexes from [8].     

Linear extension majority cycles in height-1 orders

For points x and y in a poset (X, >) let x> _p y mean that more linear extensions of the poset have x above y than y above x. It has been known for some time that > _p can have cycles when the height of the poset is two or more. Moreover, the smallest posets with a > _p cycle have nine points and heights of 2, 3 and 4. We show here that height-1 posets can also have > _p cycles. Our smallest example for this phenomenon has 15 points.Research supported through a fellowship from the Center for Advanced Study of the University of Delaware.     

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.     

Variable target value relaxed alternating projection method

In this paper we propose a modification of the von Neumann method of alternating projection x _k+1=P _A P _B x _k where A,B are closed and convex subsets of a real Hilbert space ℋ. If Fix P _A P _B ≠∅ then any sequence generated by the classical method converges weakly to a fixed point of the operator T=P _A P _B . If the distance δ=inf  _x∈A,y∈B ‖ x−y ‖ is known then one can efficiently apply a modification of the von Neumann method, which has the form x _k+1=P _A (x _k +λ _k (P _A P _B x _k −x _k )) for λ _k >0 depending on x _k (for details see: Cegielski and Suchocka, SIAM J. Optim. 19:1093–1106, 2008). Our paper contains a generalization of this modification, where we do not suppose that we know the value δ. Instead of δ we apply its approximation which is updated in each iteration.     

On projectively normal embeddings of generalk-gonal curves

Fix integersg, k andt witht>0,k≥3 andtk<g/2−1. LetX be a generalk-gonal curve of genusg andR∈Pic ^k (X) the uniqueg _k ¹ onX. SetL:=K _X⊗(R ^*)^⊗t.L is very ample. Leth _L:X→P(H ⁰(X, L)^*) be the associated embedding. Here we prove thath _L(X) is projectively normal. Ifk≥4 andtk<g/2−2 the curveh _L(X) is scheme-theoretically cut out by quadrics. The author was partially supported by MURST and GNSAGA of CNR (Italy).