Eventual partition of conserved quantities in wave motion

Let u be a classical solution to the wave equation in an odd number n of space dimensions, with compact spatial support at each fixed time. Duffin (J. Math. Anal. Appl.32 (1970), 386–391) uses the Paley-Wiener theorem of Fourier analysis to show that, after a finite time, the (conserved) energy of u is partitioned into equal kinetic and potential parts. The wave equation actually has $\text{(n + 2)(n + 3)}\text{2}$ independent conserved quantities, one for each of the standard generators of the conformal group of (n + 1)-dimensional Minkowski space. Of concern in this paper is the “zeroth inversional quantity” I₀, which is commonly used to improve decay estimates which are obtained using conservation of energy. We use Duffin's method to partition I₀ into seven terms, each of which, after a finite time, is explicitly given as a constant-coefficient quadratic function of the time. Zachmanoglou has shown that under the above assumptions if n ? 3, the spatial L² norm of u is eventually constant. A consequence of the analysis here is a bound on this constant in terms of the energy and the radius of the support of the Cauchy data of u at a fixed time.     

A personnel assignment problem

The following personnel assignment problem is considered. Let (T, ?) be a linearly ordered set where T is a set (of people), and let (P, ?) be a partially ordered set where P, a set of positions of two types, is of the same cardinality as T. Each person i in T is to be assigned to a position. A feasible assignment of personnel to positions is an embedding of (P, ?) in (T, ?). Given measures of each person's effectiveness in both types of positions, an optimal assignment maximizes the total measure of effectiveness. The general assignment problem is shown to be NP-complete. O(n log n) algorithms for two special cases of the problem are presented.     

A note on cake cutting

The algorithmic aspects of the following problem are investigated: n (≥2) persons want to cut a cake into n shares so that every person will get at least 1/n of the cake by his own measure and so that the number of cuts made on the cake is minimal. The cutting process is to be governed by a protocol (computer program). It is shown that no deterministic protocol exists which is fair (in a sense defined in the text) and results in at most n ? 1 cuts. An O(n log n)-cut deterministic protocol and an O(n)-cut randomized protocol are given explicitly and a deterministic fair protocol with 4 cuts for n=4 is described in the appendix.     

Cayley's anticipation of a generalised Cayley-Hamilton theorem

The principal result of Cayley's famouus memoir on matrices of 1858 is his contribution to what is now known as ‘the Cayley-Hamilton theorem’. We discuss this theorem and show that prior to its publication Cayley was aware of a more general theorem, a result that he left unpublished. This theorem is associated with the binary algebraic form det (μP ? λQ) analogous to the standard characteristic polynomial det (A ? λI).     

Sometimes effective Thue-Siegel-Roth-Schmidt-Nevanlinna bounds,or better

This paper will do the following: (1) Establish a (better than) Thue-Siegel-Roth-Schmidt theorem bounding the approximation of solutions of linear differential equations over valued differential fields; (2) establish an effective better than Thue-Siegel-Roth-Schmidt theorem bounding the approximation of irrational algebraic functions (of one variable over a constant field of characteristic zero) by rational functions; (3) extend Nevanlinna's Three Small Function Theorem to an n small function theorem (for each positve integer n), by removing Chuang's dependence of the bound upon the relative “number” of poles and zeros of an auxiliary function; (4) extend this n Small Function Theorem to the case in which the n small functions are algebroid (a case which has applications in functional equations); (5) solidly connect Thue-Siegel-Roth-Schmidt approximation theory for functions with many of the Nevanlinna theories. The method of proof is (ultimately) based upon using a Thue-Siegel-Roth-Schmidt type auxiliary polynomial to construct an auxiliary differential polynomial.     

An embedding theorem for regular Mal'tsev categories

In this paper, we obtain a non-abelian analogue of Lubkin's embedding theorem for abelian categories. Our theorem faithfully embeds any small regular Mal'tsev category $\mathbb{C}$ in an n-th power of a particular locally finitely presentable regular Mal'tsev category. The embedding preserves and reflects finite limits, isomorphisms and regular epimorphisms, as in the case of Barr's embedding theorem for regular categories. Furthermore, we show that we can take n to be the (cardinal) number of subobjects of the terminal object in $\mathbb{C}$.     

A sampling theorem for multivariate stationary processes

The notion of sampling for second-order q-variate processes is defined. It is shown that if the components of a q-variate process (not necessarily stationary) admits a sampling theorem with some sample spacing, then the process itself admits a sampling theorem with the same sample spacing. A sampling theorem for q-variate stationary processes, under a periodicity condition on the range of the spectral measure of the process, is proved in the spirit of Lloy's work. This sampling theorem is used to show that if a q-variate stationary process admits a sampling theorem, then each of its components will admit a sampling theorem too.     

Connectedness and classification of certain graphs

G. A. Dirac gives a necessary arc family condition for a graph to be n-vertex connected. The converse of this theorem of Dirac is false. Mesner and Watkins obtained partial results for additional conditions that the converse be true. A graph G which satisfies Dirac's arc family condition is now completely classified in terms of the order of V(G), the structure of parts of minimum cutsets of G and consequent lower bounds for vertex-connectivity of G. Examples show that all lower bounds are best possible. Several distinct extensions of Whitney's necessary and sufficient condition for a graph to be n-vertex connected also appear as corollaries. Finally, examples are presented to show a graph which satisfies a given n-family arc condition. However, the same graph does not satisfy a very similar (n ? 1)-family arc condition where exactly one arc has been eliminated from the statement of the original n-family arc conditon.     

A family of minimax estimators of a multivariate normal mean

Let X be a p-dimensional normal random vector with unknown mean vector θ and covariance σ²I. Let S/σ², independent of X, be chi-square with n degrees of freedom. Relative to the squared error loss, James and Stein (1961) have obtained an estimator which dominates the usual estimator X. Baranchik (1970) has extended James and Stein's results. We obtain a theorem which can provide a different family of minimax estimators containing James-Stein's estimator. Two interesting minimax estimators are presented in this paper.     

Statistical convergence and ideal convergence for sequences of functions

Let I⊂P(N) stand for an ideal containing finite sets. We discuss various kinds of statistical convergence and I-convergence for sequences of functions with values in R or in a metric space. For real valued measurable functions defined on a measure space (X,M,μ), we obtain a statistical version of the Egorov theorem (when μ(X)<∞). We show that, in its assertion, equi-statistical convergence on a big set cannot be replaced by uniform statistical convergence. Also, we consider statistical convergence in measure and I-convergence in measure, with some consequences of the Riesz theorem. We prove that outer and inner statistical convergences in measure (for sequences of measurable functions) are equivalent if the measure is finite.     

Sets on which several measures agree

It is known that, given n non-atomic probability measures on the space I = [0, 1], and a number α between 0 and 1, there exists a subset K of I that has measure α in each measure. It is proved here that K may be chosen to be a union of at most n intervals. If the underlying space is the circle S¹ instead of I, then K may be chosen to be a union of at most n ? 1 intervals. These results are shown to be best possible for all irrational and many rational values of α. However, there remain many rational values of α for which we are unable to determine the minimum number of intervals that will suffice.     

A classification of 4-connected graphs

Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K₂ by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, K_n+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs.     

On Reid's characterization of the ternary matroids

In this paper we prove a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3)). In particular, we prove that a matroid is ternary if it has no seriesminor of type L_n for n ≥ 5 (n cells and n circuits, each of size n ? 1), and no series-minor of type $\text{L}{}_5{}^1$ (dual of L₅), BII (Fano matroid) or BI (dual of type BII). The proof we give does not assume Reid's theorem. Rather we give a direct proof based on the methods (notably the homotopy theorem) developed by Tutte for proving his characterization of regular matroids. Indeed, the steps involved in our proof closely parallel Tutte's proof, but carrying out these steps now becomes much more complicated.     

Quantitative uniform distribution results for geometric progressions

By a classical theorem of Koksma the sequence of fractional parts ({x ⁿ }) _n≥1 is uniformly distributed for almost all values of x > 1. In the present paper we obtain an exact quantitative version of Koksma’s theorem, by calculating the precise asymptotic order of the discrepancy of \({\left( {\{ \xi {x^{{s_n}}}\} } \right)_{n \geqslant 1}}\) for typical values of x (in the sense of Lebesgue measure). Here ξ > 0 is an arbitrary constant, and (s _n ) _n≥1 can be any increasing sequence of positive integers.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Generalized controllability and inertia theory

Recently the idea of controllability has been used to generalize Lyapunov's theorem and the main inertia theorem. Corresponding results are established in this paper for a large class of linear transformations on the space of n×n Hermitian matrices.     

Another proof of dilworth's decomposition theorem

Dilworth's famous theorem [1] states that if the maximal sized antichains of a finite poset X have n elements, then X can be covered by n chains. The number n is called the width of X. Apart from proofs relating the theorem to other key theorems of combinatorics (see [1–4]), there have been a number of direct proofs (see [1, 2, 5, 6]). The shortest of these is the one by Perles [5], the outline of which is as follows.     

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

In the cake cutting problem, n≥2 players want to cut a cake into n pieces so that every player gets a ‘fair’ share of the cake by his own measure. We prove the following result: For every ε>0, there exists a cake division scheme for n players that uses at most c_εn cuts, and in which each player can enforce to get a share of at least (1-ε)/n of the cake according to his own private measure. * Partially supported by Institute for Theoretical Computer Science, Prague (project LN00A056 of MŠMT ČR) and grant IAA1019401 of GA AV ČR.     

Vitali type convergence theorems for Banach space valued integrals

Let(Ω,Σ,μ)be a complete probability space and let X be a Banach space.We introduce the notion of scalar equi-convergence in measure which being applied to sequences of Pettis integrable functions generates a new convergence theorem.We also obtain a Vitali type I-convergence theorem for Pettis integrals where I is an ideal on N.     

The set of irreducible graphs for the projective plane is finite

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K_{3, 3}. For positive integer n, let I_n (P) denote a smallest set of graphs whose maximal valency is n and such that any graph which does not embed in the real projective plane contains a subgraph homeomorphic to a graph in I_n (P) for some n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃ (P), and Glover and Huneke proved that I_n (P) is finite for all n. This note proves that I_n (P) is empty for all but a finite number of n. Hence there is a finite set of graphs for the projective plane analogous to Kuratowski's two graphs for the plane.