On the h-triangles of sequentially (S r ) simplicial complexes via algebraic shifting

Recently, Haghighi, Terai, Yassemi, and Zaare-Nahandi introduced the notion of a sequentially (S _r ) simplicial complex. This notion gives a generalization of two properties for simplicial complexes: being sequentially Cohen–Macaulay and satisfying Serre’s condition (S _r ). Let Δ be a (d?1)-dimensional simplicial complex with Γ(Δ) as its algebraic shifting. Also let (h _i,j (Δ))_{0≤j≤i≤d} be the h-triangle of Δ and (h _i,j (Γ(Δ)))_{0≤j≤i≤d} be the h-triangle of Γ(Δ). In this paper, it is shown that for a Δ being sequentially (S _r ) and for every i and j with 0≤j≤i≤r?1, the equality h _i,j (Δ)=h _i,j (Γ(Δ)) holds true.     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

Galois Groups of Generalized Iterates of Generic Vectorial Polynomials

Let q=p^u>1 be a power of a prime p, and let k_q be an overfield of GF(q). Let m>0 be an integer, let J^* be a subset of {1,…,m}, and let E^*_{m, q}(Y)=Y^qm+∑_j∈J^*X_jY^qm−j where the X_j are indeterminates. Let J³ be the set of all m−ν where ν is either 0 or a divisor of m different from m. Let s(T)=∑_0≤i≤ns_iTⁱ be an irreducible polynomial of degree n>0 in T with coefficients s_i in GF(q). Let E^*[s]_{m, q}(Y) be the generalized sth iterate of E^*_{m, q}(Y); i.e., E^*[s]_{m, q}(Y)=∑_0≤i≤ns_iE^*[i]_{m, q}(Y), where E^*[i]_{m, q}(Y), is the ordinary ith iterate. We prove that if J³⊂J^*, m is square-free, and GCD(m,n)=1=GCD(mnu,2p), then Gal(E^*[s]_{m, q},k_q({X_j:j∈j^*})=GL(m, qⁿ). The proof is based on CT (=the Classification Theorem of Finite Simple Groups) in its incarnation as CPT (=the Classification of Projectively Transitive Permutation Groups, i.e., subgroups of GL acting transitively on nonzero vectors).     

Large tactical configurations

It is shown that if r = 2, then for all m, n, h ≥ 3 and all “large enough” R, W such that mR = nW, there is a tactical configuration of rank 2 girth g = 2h, and degrees m and n on sets of cardinalities R and W. We also show that if r ≥ 3 then for all h and all compatible degree sets N = {n(i, j)≥3} and all large enough numbers R(1), R(2),…, R(r) satisfying R(i)n(i, j) = R(j)n(j, i) there is a tactical configuration of rank r, girth h, and degrees N on set with cardinalities R(1), R(2),…, R(r).     

Efficient scheduling algorithms for a single batch processing machine

Scheduling problems of a batch processing machine are solved by efficient algorithms. On a batch processing machine, multiple jobs can be processed simultaneously in a batch form. We call the number of jobs in the batch the batch size, which can be any integer between 1 and k, a predetermined integer of the maximum batch size. The process time of a batch is constant and independent of the batch size. Preemption is not allowed. Given n jobs with release times r₁ and due dates d_i, i = 1…., n, we give efficient algorithms to find a feasible schedule, if any, which minimizes the final completion time under the assumption such that for r_i > r_j, d_i ⩾ d_j. Some industrial applications are discussed.     

A system of linear equations related to the transportation problem with application to probability theory

Let P=[p_ij] be a m×n matrix and let C be the coefficient matrix of Σ_j=1ⁿ p_ijx_ij=u_i, 1≤i≤m, Σ_i=1^mp_ijx_ij=vj, 1≤j≤n. The relation between the reducibility of P and the rank of C is investigated. An application to martingale extension is given.     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

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.     

Independent cycles with limited size in a graph

Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC ₁,C ₂,...,C _k such thats ≤l(C _i ) ≤q for 1 ≤i ≤r arnds ≤l(C _i ) ≤q + 1 fork -r <i ≤k, where l(C_i) denotes the length ofC _i .     

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.     

On ARX(∞) approximation

Given data, u_j,y_j,j=1,…,n, with u_j an input sequence to a system while output is y_j, an approximation to the structure of the system generating y_j is to be obtained by regressing y_j on u_j−i,y_j−ii=1,…,p_n, where p_n increases with n. In this paper the rate of convergence of the coefficient matrices to their asymptotic values is discussed. The context is kept general so that, in particular, u_j is allowed to depend on y_i, i≤j, and no assumption of stationarity for the y_j or u_j sequences is made.     

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

We present new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related. That is, there arenjobs andmmachines; each jobjrequiresp_junits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speeds_i, it takesp_j/s_itime units. There also is a partial order on the jobs, wherej kimplies that jobkmay not start processing until jobjhas been completed. We consider two objective functions:C_max = max_j C_j, whereC_jdenotes the completion time of jobj, and ∑_jw_jC_j, wherew_jis a weight that is given for each jobj. For the first objective, the best previously known result is an -approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(log m)-approximation algorithm. We also show how to extend this result to obtain anO(log m)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release dater_jbefore which the job may not begin processing. In addition, we obtain stronger performance guarantees if there are a limited number of distinct speeds. Our results are based on a new linear programming-based technique for estimating the speed at which each job should be run, and a variant of the list scheduling algorithm of Graham that can exploit this additional information.     

Elasticity of factorizations in R 0 + X R1 + … + X lRl [X]

For an atomic domain R the elasticity ρ(R) is defined by ρ(R) = sup{m/n ¦ u₁ … u _m = v ₁ … v_n where u_i, v_i ∈ R are irreducible}. Let R ₀ ? … ? R _l be an ascending chain of domains which are finitely generated over ? and assume that R _l is integral over R ₀. Let X be an indeterminate. In this paper we characterize all domains D of the form D = R ₀ + XR₁ + … + X^lR_l[X] whose elasticity ρ(D) is finite.     

Connected Baranyai’s theorem

Let K _n ^h = (V, ( _h ^V )) be the complete h-uniform hypergraph on vertex set V with ¦V¦ = n. Baranyai showed that K _n ^h can be expressed as the union of edge-disjoint r-regular factors if and only if h divides rn and r divides \((_{h - 1}^{n - 1} )\) . Using a new proof technique, in this paper we prove that λK _n ^h can be expressed as the union \(\mathcal{G}_1 \cup ... \cup \mathcal{G}_k \) of k edge-disjoint factors, where for 1≤i≤k, \(\mathcal{G}_i \) is r _i -regular, if and only if (i) h divides r _i n for 1≤i≤k, and (ii) \(\sum\nolimits_{i = 1}^k {r_i = \lambda (_{h - 1}^{n - 1} )} \) . Moreover, for any i (1≤i≤k) for which r _i ≥2, this new technique allows us to guarantee that \(\mathcal{G}_i \) is connected, generalizing Baranyai’s theorem, and answering a question by Katona.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

Band matrices with Toeplitz inverses

It is shown that a square band matrix H=(h_ij) with h_ij=0 for j? i>r and i?j>s, where r+s is less than the order of the matrix, has a Toeplitz inverse if and only if it has a special structure characterized by two polynomials of degrees r and s, respectively.