Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

An algorithm for associative bilinear forms

We establish the equivalence between the problem of existence of associative bilinear forms and the problem of solvability in commutative power-associative finite-dimensional nil-algebras. We use the tensor product to find sufficient and necessary conditions to assure the existence of associative bilinear forms in an algebra A. The result gives us an algorithm to describe the space of associative bilinear forms for an algebra when its constants of structure γ_i,j,k for i,j,k=1,…,n are known.     

Multiple cross-intersecting families of signed sets

A k-signed r-set on[n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A₁,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

Strongly maximal antichains in posets

Given a collection S of sets, a set S∈S is said to be strongly maximal in S if |T?S|≤|S?T| for every T∈S. In Aharoni (1991) [3] it was shown that a poset with no infinite chain must contain a strongly maximal antichain. In this paper we show that for countable posets it suffices to demand that the poset does not contain a copy of posets of two types: a binary tree (going up or down) or a “pyramid”. The latter is a poset consisting of disjoint antichains A_i,i=1,2,…, such that |A_i|=i and x<y whenever x∈A_i,y∈A_j and j<i (a “downward” pyramid), or x<y whenever x∈A_i,y∈A_j and i<j (an “upward” pyramid).     

A short proof of a cross-intersection theorem of Hilton

Families A₁,…,A_k of sets are said to be cross-intersecting if for any A_i∈A_i and A_j∈A_j, i≠j. A nice result of Hilton that generalises the Erd?s-Ko-Rado (EKR) Theorem says that if r≤n/2 and A₁,…,A_k are cross-intersecting sub-families of , then

     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

Splitting multidimensional necklaces

The well-known “splitting necklace theorem” of Alon [N. Alon, Splitting necklaces, Adv. Math. 63 (1987) 247-253] says that each necklace with k⋅ai beads of color i=1,…,n, can be fairly divided between k thieves by at most n(k−1) cuts. Alon deduced this result from the fact that such a division is possible also in the case of a continuous necklace [0,1] where beads of given color are interpreted as measurable sets Ai⊂[0,1] (or more generally as continuous measures μi). We demonstrate that Alon's result is a special case of a multidimensional consensus division theorem about n continuous probability measures μ₁,…,μn on a d-cube d[0,1]. The dissection is performed by m₁+?+md=n(k−1) hyperplanes parallel to the sides of d[0,1] dividing the cube into m₁⋅?⋅md elementary cuboids (parallelepipeds) where the integers mi are prescribed in advance.     

Cyclic irreducible non-holonomic modules over the Weyl algebra: An algorithmic characterization

Let K be a field of characteristic zero, n≥1 an integer and A_n+1=K[X,Y₁,…,Y_n]〈∂_X,∂_Y1,…,∂_Yn〉 the (n+1)th Weyl algebra over K. Let S∈A_n+1 be an order-1 differential operator of the type with a_i,b_i∈K[X] and g_i∈K[X,Y_i] for every i=1,…,n. We construct an algorithm that allows one to recognize whether S generates a maximal left ideal of A_n+1, hence also whether A_n+1/A_n+1S is an irreducible non-holonomic A_n+1-module. The algorithm, which is a powerful instrument for producing concrete examples of cyclic maximal left ideals of A_n, is easy to implement and quite useful; we use it to solve several open questions.The algorithm also allows one to recognize whether certain families of algebraic differential equations have a solution in K[X,Y₁,…,Y_n] and, when they have one, to compute it.     

A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y₁,…,Y_p} of subsets of {1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M) of ordered pairs (i,j) satisfying i≠j and Y_i⊆Y_j is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.     

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum

We investigate simultaneous solutions of the matrix Sylvester equations A_iX-XB_i=C_i,i=1,2,…,k, where {A₁,…,A_k} and {B₁,…,B_k} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C₁,…,C_k} if and only if the joint spectra σ(A₁,…,A_k) and σ(B₁,…,B_k) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations.     

A random intersection digraph: Indegree and outdegree distributions

Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc i→j is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤i≤n, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m→∞.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Perfect Skolem sets

A Skolem sequence is a sequence s₁,s₂,…,s_2n (where s_i∈A={1,…,n}), each s_i occurs exactly twice in the sequence and the two occurrences are exactly s_i positions apart. A set A that can be used to construct Skolem sequences is called a Skolem set. The problem of deciding which sets of the form A={1,…,n} are Skolem sets was solved by Thoralf Skolem in the late 1950s. We study the natural generalization where A is allowed to be any set of n positive integers. We give necessary conditions for the existence of Skolem sets of this generalized form. We conjecture these necessary conditions to be sufficient, and give computational evidence in favor of our conjecture. We investigate special cases of the conjecture and prove that the conjecture holds for some of them. We also study enumerative questions and show that this problem has strong connections with problems related to permutation displacements.     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

Quantum effects, sequential independence and majorization

A quantum effect is a positive Hilbert space contraction operator. If {E_i}, 1?i?n, are n quantum effects (defined on some Hilbert space H), then their sequential product is the operator . It is proved that the quantum effects {E_i}, 1?i?n, are sequentially independent if and only if for every permutation r₁r₂…r_n of the set S_n={1,2,…,n}. The sequential independence of the effects E_i, 1?i?n, implies E_noE_n-1o…oE_j+1oE_jo…oE₁=(E_noE_n-1o…E_j+1)oE_jo…oE₁ for every 1?j?n. It is proved that if there exists an effect E_j, 1?j?n, such that E_j?(E_noE_n-1o…E_j+1)oE_jo…oE₁, then the effects {E_i} are sequentially independent and satisfy .