Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

<Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis>,exp</Subscript> Does Not Prove NP = <Emphasis Type="Italic">co</Emphasis>-NP Uniformly

The notion of a uniform sequent-calculus proof is introduced. It is shown that a strengthening, S_k,exp , of the well-studied bounded arithmetic system S_k of Buss does not prove NP = co-NP with a uniform proof. A slightly stronger result that S_k,exp cannot prove uniformly for 2 ≤ k′ ≤ k is also established. A modification of the technique used is applied to show that S_k,exp is unable to prove the Davis-Putnam-Robinson-Matiyasevich theorem. Generalizations of these results to higher levels of the Grzegorczyck hierarchy are presented. Bibliography: 21 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 99–120.     

On list incidentor (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">l</Emphasis>)-coloring

A proper incidentor coloring is called a (k, l)-coloring if the difference between the colors of the final and initial incidentors ranges between k and l. In the list variant, the extra restriction is added: the color of each incidentor must belong to the set of admissible colors of the arc. In order to make this restriction reasonable we assume that the set of admissible colors for each arc is an integer interval. The minimum length of the interval that guarantees the existence of a list incidentor (k, l)-coloring is called a list incidentor (k, l)-chromatic number. Some bounds for the list incidentor (k, l)-chromatic number are proved for multigraphs of degree 2 and 4.     

Cyclic codes over <Emphasis Type="Italic">R</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript>

Cyclic codes over an infinite family of rings are defined. The general properties of cyclic codes over these rings are studied, in particular nontrivial one-generator cyclic codes are characterized. It is also proved that the binary images of cyclic codes over these rings under the natural Gray map are binary quasi-cyclic codes of index 2 ^k . Further, several optimal or near optimal binary codes are obtained from cyclic codes over R _k via this map.     

The Existence of LHMTS(<Emphasis Type="Italic">m</Emphasis><Superscript><Emphasis Type="Italic">v</Emphasis></Superscript>) and LHDTS(<Emphasis Type="Italic">m</Emphasis><Superscript><Emphasis Type="Italic">v</Emphasis></Superscript>)

In this article, we establish the existence of an LHMTS(m^v) for v ≡ 2 (mod 6) and m≡ 3 (mod 6). Thus there exists an LHMTS(m^v) if and only if v(v-1)m² ≡ 0 (mod 3) except possibly for v=6, m≡ 1, 5 (mod 6) and m≠1. In the similar way, the existence of LHDTS(m^v) is completely determined, i.e., there exists an LHDTS(m^v) if and only if v(v-1)m² ≡ 0 (mod 3).     

On the family of diophantine triples {<Emphasis Type="Italic">k</Emphasis> + 1, 4<Emphasis Type="Italic">k</Emphasis>, 9<Emphasis Type="Italic">k</Emphasis> + 3}

We prove that if k is a positive integer and d is a positive integer such that the product of any two distinct elements of the set {k + 1, 4k, 9k + 3, d} increased by 1 is a perfect square, then d = 144k ³ + 192k ² + 76k + 8.      

Continuous <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">p</Emphasis></Subscript>-symmetric distributions

For p > 0, the l _n,p -generalized surface measure on the l _n,p -unit sphere is studied and used for deriving a geometric measure representation for l _n,p -symmetric distributions having a density.     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

(<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-bi-Koszul algebras

The paper focuses on the 1-generated positively graded algebras with non-pure resolutions and mainly discusses a new kind of algebras called(s,t,d)-bi-Koszul algebras as the generalization of bi-Koszul algebras. An(s,t,d)-bi-Koszul algebra can be obtained from two periodic algebras with pure resolutions. The generation of the Koszul dual of an(s,t,d)-bi-Koszul algebra is discussed. Based on it,the notion of strongly(s,t,d)-bi-Koszul algebras is raised and their homological properties are further discussed.     

Limit theorems for inverse process <Emphasis Type="Italic">T</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> of Hawkes process

We consider linear Hawkes process N _t and its inverse process T _n . The limit theorems for N _t are well known and studied by many authors. In this paper, we study the limit theorems for T _n . In particular, we investigate the law of large numbers, the central limit theorem and the large deviation principle for T _n . The main tool of the proof is based on immigration-birth representation and the observations on the relation between N _t and T _n .     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

Approximation of sine-shaped functions by constants in the spaces <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>, <Emphasis Type="Italic">p</Emphasis> < 1

We investigate the best approximations of sine-shaped functions by constants in the spaces L_p for p < 1. In particular, we find the best approximation of perfect Euler splines by constants in the spaces L_p for certain p(0,1).Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 6, pp. 745–762, June, 2004.     

Cyclotomic Hecke Algebras of <Emphasis Type="Italic">G</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, <Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)

In this note, we find a monomial basis of the cyclotomic Hecke algebra \({\mathcal{H}_{r,p,n}}\) of G(r,p,n) and show that the Ariki-Koike algebra \({\mathcal{H}_{r,n}}\) is a free module over \({\mathcal{H}_{r,p,n}}\), using the Gröbner-Shirshov basis theory. For each irreducible representation of \({\mathcal{H}_{r,p,n}}\), we give a polynomial basis consisting of linear combinations of the monomials corresponding to cozy tableaux of a given shape.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

The <Emphasis Type="Italic">p</Emphasis>-Adic order of the <Emphasis Type="Italic">k</Emphasis>-Fibonacci and <Emphasis Type="Italic">k</Emphasis>-Lucas numbers

Let (F _k,n ) _n and (L _k,n )n be the k-Fibonacci and k-Lucas sequence, respectively, which satisfies the same recursive relation a _n+1 = ka _n + a _n?1 with initial values F _k,0 = 0, F _k,1 = 1, L _k,0 = 2 and L _k,1 = k. In this paper, we characterize the p-adic orders ν _p (F _k,n ) and ν _p (L _k,n ) for all primes p and all positive integers k.     

The existence and nonexistence of entire positive solutions of semilinear elliptic systems with gradient term

We show the existence and nonexistence of entire positive solutions for semilinear elliptic system with gradient term Δu+|∇u|=p(|x|)f(u,v), Δv+|∇v|=q(|x|)g(u,v) on RN, N?3, provided that nonlinearities f and g are positive and continuous, the potentials p and q are continuous, c-positive and satisfy appropriate growth conditions at infinity. We find that entire large positive solutions fail to exist if f and g are sublinear and p and q have fast decay at infinity, while if f and g satisfy some growth conditions at infinity, and p, q are of slow decay or fast decay at infinity, then the system has infinitely many entire solutions, which are large or bounded.     

Convergence of greedy algorithm in Walsh system in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>

Convergence of the greedy algorithm in Walsh system in L _p , p > 1 is studied. It is proved that there exists a function in L _p , 1 < p < 2, with greedy algorithm not converging in measure to that function. A continuous function with divergent in L _p , p > 2, greedy algorithm is constructed and sufficient conditions for convergence of the greedy algorithm in L _p , p > 1 are given.     

(<Emphasis Type="Italic">T</Emphasis>, <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">i</Emphasis></Subscript>) Policy Inventory Model for Deteriorating Items with Time Proportional Demand

An EOQ model is reconsidered here in which the demand rate is changing linearly with time and the deterioration is assumed to be a constant fraction of the onhand inventory. The planning horizon is finite and known and the replenishment periods are assumed to be constant. The problem is to find the optimal number of replenishments, which are instantaneous. When there is no deterioration, the model developed is related to the corresponding model for nondeteriorating items. An example followed by sensitivity analysis is given to illustrate the derived results.     

(<Emphasis Type="Italic">q</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">q</Emphasis><Subscript>2</Subscript>)-quasimetrics bi-Lipschitz equivalent to 1-quasimetrics

We prove that the conditions of (q₁, 1)- and (1, q₂)-quasimertricity of a distance function ρ are sufficient for the existence of a quasimetric bi-Lipschitz equivalent to ρ. It follows that the Box-quasimetric defined with the use of basis vector fields of class C₁ whose commutators at most sum their degrees is bi-Lipschitz equivalent to some metric. On the other hand, we show that these conditions are not necessary. We prove the existence of (q₁, q₂)-quasimetrics for which there are no Lipschitz equivalent 1-quasimetrics, which in particular implies another proof of a result by V. Schröder.