On the maximum empty rectangle problem

Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n²) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)²) expected time.     

Random A-permutations: Convergence to a Poisson process

Suppose that S _n is the permutation group of degree n, A is a subset of the set of natural numbers ?, and T _n(A) is the set of all permutations from S _n whose cycle lengths belong to the set A. Permutations from T _n are usually called A-permutations. We consider a wide class of sets A of positive asymptotic density. Suppose that ζ _mn is the number of cycles of length m of a random permutation uniformly distributed on T _n. It is shown in this paper that the finite-dimensional distributions of the random process {tz _mn, m ε A} weakly converge as n → ∞ to the finite-dimensional distributions of a Poisson process on A.     

The class A(R,S) of (0, 1)-matrices

Let R and S be two vectors whose components are m and n non-negative integers, respectively. Let $\text{A}$(R, S) be the class consisting of all (0, 1)-matrices of size m by n with row sum vector R and column sum vector S. In this paper we derive a lower bound to the cardinality of the class $\text{A}$(R, S), which can be computed readily.     

Generalized involution models for wreath products

We prove that if a finite group H has a generalized involution model, as defined by Bump and Ginzburg, then the wreath product H ? S _n also has a generalized involution model. This extends the work of Baddeley concerning involution models for wreath products. As an application, we construct a Gel’fand model for wreath products of the form A ? S _n with A abelian, and give an alternate proof of a recent result due to Adin, Postnikov and Roichman describing a particularly elegant Gel’fand model for the wreath product ? _r ? S _n . We conclude by discussing some notable properties of this representation and its decomposition into irreducible constituents, proving a conjecture of Adin, Postnikov and Roichman.     

The endomorphism spectrum of a monounary algebra

The endomorphism spectrum specA of an algebra A is defined as the set of all positive integers, which are equal to the number of elements in an endomorphic image of A, for all endomorphisms of A. In this paper we study finite monounary algebras and their endomorphism spectrum. If a finite set S of positive integers is given, one can look for a monounary algebra A with S = specA. We show that for countably many finite sets S, no such A exists. For some sets S, an appropriate A with spec A = S are described. For n ∈ ? it is easy to find a monounary algebra A with {1, 2, ..., n} = specA. It will be proved that if i ∈ ?, then there exists a monounary algebra A such that specA skips i consecutive (consecutive eleven, consecutive odd, respectively) numbers. Finally, for some types of finite monounary algebras (binary and at least binary trees) A, their spectrum is shown to be complete.     

Controllable Subsets in Graphs

Let X be a graph on ?? vertices with adjacency matrix A, and let S be a subset of its vertices with characteristic vector z. We say that the pair (X, S) is controllable if the vectors A ^r z for r =? 1, . . . , ?? ? 1 span ${\mathbb{R}^{\nu}}$ . Our concern is chiefly with the cases where S =?V(X), or S is a single vertex. In this paper we develop the basic theory of controllable pairs. We will see that if (X, S) is controllable then the only automorphism of X that fixes S as a set is the identity. If (X, S) is controllable for some subset S then the eigenvalues of A are all simple.     

Generalized euler-type partition identities

Let A and S be subsets of the natural numbers. Let A′(n) be the number of partitions of n where each part appears exactly m times for some m?A. Let S(n) be the number of partitions of n into parts which are elements of S.     

On a problem of Katona on minimal separating systems

Let S be an n-element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S{A₁,A₂,…,A_f(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that A_k ∩ A_l= ?, and x ∈ A_k, y ∈ A_l. In particular it is shown that f(n)= 3 log₃n when n is a power of 3.     

Intersection problems and integral equivalence

Let A and B be matrices over a principal ideal domain, Π. Necessary conditions, involving the invariant factors of A and B, are given for B to be a submatrix of A or a principal submatrix of A.If a given nonnegative integral matrix, B, is the intersection matrix of a pair of families of subsets of an n-set, and n is the smallest integer for which this is true, we say that the content of B is n. In that event, B is a submatrix of K(n), the intersection matrix of all subsets of an n-set. More refined results are obtained in certain cases by considering S(n, k, l), the intersection matrix of the k-subsets of an n-set versus its l-subsets. The invariant factors of K(n) and S(n, k, l) are calculated and it is shown how this information may be used to get lower bounds for the content of B. In the more widely studied symmetric version of the content problem, B must be a principal submatrix of K(n) or, possibly, S(n, k) = S(n, k, k). In this case, the invariant factors of K(n) ? xI or S(n, k) ? xI also provide relevant information.     

Simple image set of linear mappings in a max-min algebra

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set S_A consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of S_A is a subset of the set of all eigenvectors of A. In the general case, there is a permutation π, such that the closure of S_A is a subset of the set of all eigenvectors permuted by π. The simple image set of the matrix square and the topological aspects of the problem are also described.     

Nonadaptive search problem with sets of equal sum

Consider the set A={1,2,3,…,2 ⁿ }, n≥3 and let x∈ A be unknown element. For given natural number S we are allowed to ask whether x belongs to a subset B of A such that the sum of the elements of B equals S. We investigate for which S it is possible to find x using a nonadaptive search.     

Normal coverings of finite symmetric and alternating groups

In this paper we investigate the minimum number of maximal subgroups Hi, i=1,…,k of the symmetric group Sn (or the alternating group An) such that each element in the group Sn (respectively An) lies in some conjugate of one of the Hi. We prove that this number lies between a?(n) and bn for certain constants a,b, where ?(n) is the Euler phi-function, and we show that the number depends on the arithmetical complexity of n. Moreover in the case where n is divisible by at most two primes, we obtain an upper bound of 2+?(n)/2, and we determine the exact value for Sn when n is odd and for An when n is even.     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

The left and right inverse eigenvalue problems of generalized reflexive and anti-reflexive matrices

Let n×n complex matrices R and S be nontrivial generalized reflection matrices, i.e., R^∗=R=R⁻¹≠±I_n, S^∗=S=S⁻¹≠±I_n. A complex matrix A with order n is said to be a generalized reflexive (or anti-reflexive ) matrix, if RAS=A (or RAS=−A). In this paper, the solvability conditions of the left and right inverse eigenvalue problems for generalized reflexive and anti-reflexive matrices are derived, and the general solutions are also given. In addition, the associated approximation solutions in the solution sets of the above problems are provided. The results in present paper extend some recent conclusions.     

A central limit theorem for mixing stationary point processes

Suppose A₀ is a strictly stationary, second order point process on Z^d that is ?-mixing. The particles initially present are then continually subjected to random translations via random walks. If A_n is the point process resulting at time n, then we prove, under certain technical conditions, that the total occupation time by time n of a finite nonempty subset B of Z^d, namely, S_n(B)=Σⁿ_k=1A_k(B), is asymptotically normally distributed.     

Noisy colored point set matching

We propose a process for determining approximated matches, in terms of the bottleneck distance, under color preserving rigid motions, between two colored point sets A,B∈R², |A|≤|B|. We solve the matching problem by generating all representative motions that bring A close to a subset B^′ of set B and then using a graph matching algorithm. We also present an approximate matching algorithm with improved computational time. In order to get better running times for both algorithms we present a lossless filtering preprocessing step. By using it, we determine some candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B^′ of S. Then, we solve the matching problem between A and every candidate zone. Experimental results using both synthetic and real data are reported to prove the effectiveness of the proposed approach.     

Spectral criteria for complementary triangular forms

In this paper we consider the following problem: Given two matricesA,Z∈? ^n×n , does there exist an invertiblen×n-matrixS such thatS ^?1 AS is an upper triangular matrix andS ^?1 ZS is a lower triangular matrix, and if so, what can be said about the order in which the eigenvalues ofA andZ appear on the diagonals of these triangular matrices? For special choices ofA andZ a complete solution is possible, as has been shown by several authors. Here we follow a lead, provided by Shmuel Friedland, who discussed the case where bothA andZ have at leastn-1 linearly independent eigenvectors, and we descibe the problem in terms of Jordan chains and left-Jordan chains for the matricesA, Z. The results give some insight in the question why certain classes of matrices (like the nonderogatory and the rank 1 matrices) allow for a detailed solution of the problems described above; for some of these classes the result of this analysis is presented here for the first time.     

Sieve-equivalence and explicit bijections

Suppose A₁,…, A_n are subsets of a finite set A, and B₁,…, B_n are subsets of a finite set B. For each subset S of N = {1, 2,…, n}, let A_s = ∩_i?SA_i and B_S = ∩_i?SB_i. It is shown that if explicit bijections f_S:A_S → B_S for each S ? N are given, an explicit bijection h:A-∪_i=1A_i→B-∪_i=1B_i can be constructed. The map h is independent of any ordering of the elements of A and B, and of the order in which the subsets A_i and B_i are listed.     

Answers to two questions posed by Farhi concerning additive bases

Let A be an asymptotic basis for N and X a finite subset of A such that A?X is still an asymptotic basis. Farhi recently proved a new batch of upper bounds for the order of A?X in terms of the order of A and a variety of parameters related to the set X. He posed two questions concerning possible improvements to his bounds. In this note, we answer both questions.     

On Supersets of Wavelet Sets

Considering a single dyadic orthonormal wavelet ψ in L ²(?), it is still an open problem whether the support of $\widehat{\psi}$ always contains a wavelet set. As far as we know, the only result in this direction is that if the Fourier support of a wavelet function is “small” then it is either a wavelet set or a union of two wavelet sets. Without assuming that a set S is the Fourier support of a wavelet, we obtain some necessary conditions and some sufficient conditions for a “small” set S to contain a wavelet set. The main results, which are in terms of the relationship between two explicitly constructed subsets A and B of S and two subsets T ₂ and D ₂ of S intersecting itself exactly twice translationally and dilationally respectively, are (1) if $A\cup B\not\subseteq T_{2}\cap D_{2}$ then S does not contain a wavelet set; and (2) if A∪B?T ₂∩D ₂ then every wavelet subset of S must be in S?(A∪B) and if S?(A∪B) satisfies a “weak” condition then there exists a wavelet subset of S?(A∪B). In particular, if the set S?(A∪B) is of the right size then it must be a wavelet set.