Multi-latin squares

A multi-latin square of order n and index k is an n×n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in k-latin square of order m embeds in a k-latin square of order n, for each n≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥k+2. We also show that for each n≥1, there exists some finite value g(n) such that for all k≥g(n), every k-latin square of order n is separable.We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.     

On a duel with time lag and arbitrary accuracy functions

This paper deals with a two-person zero-sum game called duel with the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at his opponent. If I or II fires at timex, he hits his opponent with probabilityp (x) orq(x), respectively. The gun of I is silent, and hence, II does not know whether his opponent has fired or not, and the gun of II is noisy with time lagt, wheret is a positive constant,i.e., if II fires at timex then I knows it at timex +t. Further, if I hits II without being hit himself before, the payoff is 1; if I is hit by II without hitting II before, the payoff is ?1; if they hit each other at the same time or both survive, the payoff is 0. This paper gives optimal strategy for each player and the value of the game.     

Uniform approximation by some Hermite interpolating splines

In this paper some upper bound for the error ∥ s-f ∥_∞ is given, where f ε C¹[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(x_i) = s(x_i), f′(rmx_i) = s′(x_i), s^(j) (x_i) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots x_i are such that a = x₀ < x₁ < … < x_n = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C¹[a, b] by convex HSI is also given.     

Tromino tilings of domino-deficient rectangles

We consider tromino tilings of m×n domino-deficient rectangles, where 3|(mn−2) and m,n≥0, and characterize all cases of domino removal that admit such tilings, thereby settling the open problem posed by Ash and Golomb in [J. Marshall Ash, S. Golomb, Tiling Deficient Rectangles with Trominoes, Integre Technical Publishing Co., Mathematics Magazine (2003), 46-55]. We suggest a procedure for tiling domino-deficient rectangles based on this characterization. We also consider general 2-deficiency in n×4 rectangles, where n≥8, and characterize all pairs of missing squares which do not permit a tromino tiling.     

Generating pairs for the held groupHe

A groupG is said to be (l, m, n)-generated if it is a quotient group of the triangle groupT(p,q,r)=<x,y,z?x ^p =y ^q =z ^r =xyz=1>. In [15], the question of finding all triples (l, m, n) such that non-abelian finite simple groups are (l, m, n)-generated was posed. In this paper we partially answer this question for the sporadic groupHe. We continue the study of (p, q, r)-generations of the sporadic simple groups, where,p, q, r are distinct primes. The problem is resolved for the Held groupHe.     

Monotone factors of I.I.D. processes

LetB(p) andB(q) be Bernoulli shifts on {0, 1,...,d - 1}^ℤ. Ifh(p)>h(q), it is a classical theorem of Sinai that there is a factor map takingB(p) toB(q). If, in addition,p stochastically dominatesq, we can ask whether there is such a factor map ϕ which is monotone: ϕ(x) _i≤x_i for each coordinatei of almost every pointx. Here we show that there is a monotone finitary code fromB(p) toB(q) in the case whereB(q) is a shift on two symbols.     

Equation f(p(x)) = q(f(x)) for given real functions p, q

We investigate functional equations f(p(x)) = q(f(x)) where p and q are given real functions defined on the set ? of all real numbers. For these investigations, we can use methods for constructions of homomorphisms of mono-unary algebras. Our considerations will be confined to functions p, q which are strictly increasing and continuous on ?. In this case, there is a simple characterization for the existence of a solution of the above equation. First, we give such a characterization. Further, we present a construction of any solution of this equation if some exists. This construction is demonstrated in detail and discussed by means of an example.     

Remarks on characterization of normal and stable distributions

LetX, Y, Z be independent identically distributed (i.i.d.) random variables. Suppose $$E\left| {tX + uY + vZ} \right|^p = A(\left| t \right|^q + \left| u \right|^q + \left| v \right|^q )^{{p \mathord{\left/ {\vphantom {p q}} \right. \kern-\nulldelimiterspace} q}} $$ for all realt, u, v, whereq=2 andp≠2m (m=1, 2,...) or 0<p<q<2. It was proved by the author this impliesX, Y, Z have the symmetricq-stable distribution. For two random variables such result is not true. One may suppose that the condition $$E\left| {tX + uY} \right|^p = A(\left| t \right|^q + \left| u \right|^q )^{{p \mathord{\left/ {\vphantom {p q}} \right. \kern-\nulldelimiterspace} q}} $$ and additional assumption on the behavior ofP{|X|≥x} (x→∞) implyX, Y are stable. In this paper we show it is not valid. The second result is: if the last relation holds for two different exponents andq=2, thenX andY are normal.     

Witness Rectangle Graphs

In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

A positive answer to the basis problem

lcub;x _n rcub; with lcub;x _n ,x* _n rcub; biorthogonal is a “uniformly minimal basis with quasifixed brackets and permutations” of a Banach spaceX if lcub;x _n rcub; andx* _n rcub; are both bounded. Moreover, there is an increasing sequence lcub;q _m rcub; of positive integers such that, for eachx′ ofX, settingq′(0)=0, $$x' = \sum\limits_{m = 0}^\infty { \sum\limits_{n = q'(m) + 1}^{q'(m + 1)} {x_{\pi '(n)}^ * (x')x_{\pi '(n)} ,} } $$ , where, for eachm≥1,q(m)+1≤q′(m)≤q(m+1) while $$\left\{ {\pi '(n)} \right\}_{n = q(m) + 1}^{q(m + 1)} is a permutation of \left\{ n \right\}_{n = q(m) + 1}^{q(m + 1)} .$$ . Then, for each subspaceY of a separable Banach spaceX, there exists a uniformly minimal basis with quasi-fixed brackets and permutations ofY, which can be extended to a uniformly minimal basis with quasi-fixed brackets and permutations ofX.     

Ein konvergentes Iterationsverfahren zur Bestimmung der Nullstellen eines Polynoms

Summary In order to determine the roots of a polynomialp, a sequence of numbers {x _k} is constructed such that the associated sequence {|p(x _k)|} decreases monotonically. To determine a new iteration pointx _k+1 such that |p(x _k+1)|<-|p(x _k)| ( is a positive real constant, <1, depending only on the degree ofp), we determine a circleK aroundx _k which contains no root ofp and compute the values ofp atN points which are distributed equally on the circumference ofK (N again depends only on the degree ofp); at least one of theN points is shown to satisfy the given condition. Computing the function values by means of Fourier synthesis according to Cooley-Tukey [2] and combining our iteration step with the normal step of the method of Nickel [1], we obtain a numerically safe and fast algorithm for determining the roots of arbitrary polynomials.     

On the existence of solutions for an elliptic system of equations with arbitrary order growth

Let BR be the ball centered at the origin with radius R in RN ( N ≥2). In this paper we study the existence of solution for the following elliptic systemu -△u+λu=p/(p + q)κ(| x |)) u(p-1)vq1,x ∈BR1,-△u+λu=p/(p + q)κ(| x |)) upv(q-1)1,x ∈BR1,u > 01,v > 01,x ∈ BR1,(u)/(v)=01,(v)/(v)=01,x ∈BRwhereλ > 0 , μ > 0 p ≥ 2, q ≥ 2,ν is the unit outward normal at the boundary BR . Under certainassumptions on κ ( | x | ), using variational methods, we prove the existence of a positive and radially increasing solution for this problem without growth conditions on the nonlinearity.     

Minorations pour l'équation de Catalan

We consider Catalan's equation x^p − y^q = 1 (with p, q prime and |x|, |y| > 1). We show that, besides the obvious solution 3² − 2³ = 1, min {p; q} > 10⁵ and max {p; q} > 10⁶.     

Monotonicity of input-output mappings in inverse coefficient and source problems for parabolic equations

This article presents a mathematical analysis of input-output mappings in inverse coefficient and source problems for the linear parabolic equation ut=(kx(x)ux)+F(x,t), (x,t)∈ΩT:=(0,1)×(0,T]. The most experimentally feasible boundary measured data, the Neumann output (flux) data f(t):=−k(0)ux(0,t), is used at the boundary x=0. For each inverse problems structure of the input-output mappings is analyzed based on maximum principle and corresponding adjoint problems. Derived integral identities between the solutions of forward problems and corresponding adjoint problems, permit one to prove the monotonicity and invertibility of the input-output mappings. Some numerical applications are presented.     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

The number of vertices whose out-arcs are pancyclic in a 2-strong tournament

An arc going out from a vertex x in a digraph is called an out-arc of x. Yao et al. [Discrete Appl. Math. 99 (2000) 245-249] proved that every strong tournament contains a vertex x such that all out-arcs of x are pancyclic. Recently, Yeo [J. Graph Theory 50 (2005) 212-219] proved that each 3-strong tournament contains two such vertices. In this paper, we confirm that Yeo's result is also true for 2-strong tournaments. Our proof implies a polynomial algorithm to find two such vertices.     

Generalized Kloosterman sum with primes

The work is devoted to generalized Kloosterman sums modulo a prime, i.e., trigonometric sums of the form \(\sum\nolimits_{p \leqslant x} {\exp \left\{ {2\pi i\left( {a\bar p + {F_k}\left( p \right)} \right)/q} \right\}} \) and \(\sum\nolimits_{n \leqslant x} {\mu \left( n \right)\exp \left\{ {2\pi i\left( {a\bar n + {F_k}\left( n \right)} \right)/q} \right\}} \), where q is a prime number, \(\left( {a,q} \right) = 1,m\bar m \equiv 1\left( {\bmod {\kern 1pt} q} \right)\), F _k (u) is a polynomial of degree k ≥ 2 with integer coefficients, and p runs over prime numbers. An upper estimate with a power saving is obtained for the absolute values of such sums for x ≥ q^1/2+ε.     

Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

The problem of the partition-numbersJ _?(p, q), considered by Hadwiger and Debrunner for the family ?=C ⁿ of convex bodies, is extended to simplicial complexes and arbitrary families assuming only the validity of Helly’s theorem. We obtain results similar to those of Hadwiger and Debrunner. Further we show the existence of all partition-numbers for the family? = H ⁿC of homothets of a convex body and we get new informations on the partition-numbers for the family of parallel rectangles.