The topological type of the α-sections of convex sets

An α=(α₁,…,αk)(0?αi?1) section of a family {K₁,…,Kk} of convex bodies in Rd is a transversal halfspace H⁺ for which Vold(Ki∩H⁺)=αi⋅Vold(Ki) for every 1?i?k. Our main result is that for any well-separated family of strictly convex sets, the space of α-sections is diffeomorphic to Sd−k.     

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.     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

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.     

Unitary part of a contraction

For a contraction A on a Hilbert space H, we define the index j(A) (resp., k(A)) as the smallest nonnegative integer j (resp., k) such that ker(I−Aj∗Aj) (resp., ker(I−Ak*Ak)∩ker(I−AkAk∗)) equals the subspace of H on which the unitary part of A acts. We show that if , then j(A)?n (resp., k(A)?⌈n/2⌉), and the equality holds if and only if A is of class Sn (resp., one of the three conditions is true: (1) A is of class Sn, (2) n is even and A is completely nonunitary with ‖An−2‖=1 and ‖An−1‖<1, and (3) n is even and A=U⊕A^′, where U is unitary on a one-dimensional space and A^′ is of class Sn−1).     

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.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

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

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.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Tournament immersion and cutwidth

A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v₁,…,vn} in such a way that for each j, there are at most k edges uv such that u∈{v₁,…,vj−1} and v∈{vj,…,vn}.We prove that for every set S of tournaments, the following are equivalent:

•

there is a digraph H such that H cannot be strongly immersed in any member of S,

•

there exists k such that every member of S has cutwidth at most k,

•

there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles.

This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.     

Maps preserving the spectrum of generalized Jordan product of operators

Let A₁,A₂ be standard operator algebras on complex Banach spaces X₁,X₂, respectively. For k?2, let (i₁,…,i_m) be a sequence with terms chosen from {1,…,k}, and define the generalized Jordan product

     

Bernstein type operators having 1 and x j as fixed points

For certain generalized Bernstein operators {L _n } we show that there exist no i, j ∈ {1, 2, 3,…}, i < j, such that the functions e _i (x) = x ⁱ and e _j (x) = x ^j are preserved by L _n for each n = 1, 2,… But there exist infinitely many e _i such that e ₀(x) = 1 and e _j (x) = x _j are its fixed points.     

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.     

More on the generalized Macaulay theorem

Let k₁ ? k₂ ? … ? k_n be given positive integers and let F denote the set of vectors (l₁, …, l_n) with integer components satisfying 0 ? l_i ? k_i, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k₁ = … = k_n = 1 case which has been given independently by Katona [4] and Kruskal [5].     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.