Factoring by subsets of cardinality of prime power

Rédei's theorem asserts that if a finite abelian group is expressed as a direct product of subsets of prime cardinality, then at least one of the factors must be periodic. (A periodic subset is a direct product of some subset and a nontrivial subgroup.) A. D. Sands proved that if a finite cyclic group is the direct product of subsets each of which has cardinality that is a power of a prime, then at least one of the factors is periodic. We prove that the same conclusion holds if a general finite abelian group is factored as a direct product of cyclic subsets of prime cardinalities and general subsets of cardinalities that are powers of primes provided that the components of the group corresponding to these latter primes are cyclic.     

Hedetniemi's Conjecture and the Retracts of a Product of Graphs

We show that every core graph with a primitive automorphism group has the property that whenever it is a retract of a product of connected graphs, it is a retract of a factor. The example of Kneser graphs shows that the hypothesis that the factors are connected is essential. In the case of complete graphs, our result has already been shown in [4, 17], and it is an instance where Hedetniemi's conjecture is known to hold. In fact, our work is motivated by a reinterpretation of Hedetniemi's conjecture in terms of products and retracts.     

Field of sine-Gordon type in spacetime of arbitrary dimension: Existence of the nelson measure

A model of a field with bounded current density is investigated. It is shown that there exists an infinite-fold integral that determines a generating functional of the Schwinger functions. It is shown that this functional is the Fourier transform of a probability measure on the field trajectories that is concentrated in a Hilbert subspace of the space of tempered distributions of first order of singularity. It is shown that the field satisfies the strong regularity axiom of Osterwalder and Schrader.Moscow Power Institute. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 98, No. 1, pp. 12–28, January, 1994.     

Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

It is shown that two sorts of problems belong to the NP-complete class. First, it is proven that for a given κ-colorable graph and a given κ-coloring of that graph, determining whether the graph is or is not uniquely κ-colorable is NP-complete. Second, a result by Garey, Johnson, and Stockmeyer is extended with a proof that the coloring of four-regular planar graphs is NP-complete.     

The sequence of open and closed prefixes of a Sturmian word

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence.     

Dynamics of nonself-similar solutions of the Dawson equation

We study the dynamics of nonself-similar solutions of the Cauchy problem for a stochastic partial differential Itô equation of the parabolic type with linear principal part and with the diffusion coefficient that is exponential function whose exponent is larger than zero, but is less than 1. The equations of such a type are named the Dawson equations. It is proved that the solution that is of a nonself-similar form and is generated by a finite initial function behaves itself in the course of time analogously to a self-similar solution.     

Impacts of inquiry pedagogy on undergraduate students conceptions of the function of proof

Mathematicians and mathematics educators agree that proof is an important tool in mathematics, yet too often undergraduate students see proof as a superficial part of the discipline. While proof is often used by mathematicians to justify that a theorem is true, many times proof is used for another purpose entirely such as to explain why a particular statement is true or to show mathematics students a particular proof technique. This paper reports on a study that used a form of inquiry-based learning (IBL) in an introduction to proof course and measured the beliefs of students in this course about the different functions of proof in mathematics as compared to students in a non-IBL course. It was found that undergraduate students in an introduction to proof course had a more robust understanding of the functions of proof than previous studies would suggest. Additionally, students in the course taught using inquiry pedagogy were more likely to appreciate the communication, intellectual challenge, and providing autonomy functions of proof. It is hypothesized that these results are a response to the pedagogy of the course and the types of student activity that were emphasized.     

Automorphism groups of pictures

A picture is a simple graph together with an edge-coloring, such that each vertex is incident with exactly one edge of each color. An automorphism of a picture is a graph automorphism that preserves the colors of the edges. We show that every group is isomorphic to the full automorphism group of a picture, and prove that a group is isomorphic to a vertex-transitive subgroup of the automorphism group of a picture if and only if it can be generated by involutions.     

The rank of the endomorphism monoid of a uniform partition

The rank of a semigroup is the cardinality of a smallest generating set. In this paper we compute the rank of the endomorphism monoid of a non-trivial uniform partition of a finite set, that is, the semigroup of those transformations of a finite set that leave a non-trivial uniform partition invariant. That involves proving that the rank of a wreath product of two symmetric groups is two and then use the fact that the endomorphism monoid of a partition is isomorphic to a wreath product of two full transformation semigroups. The calculation of the rank of these semigroups solves an open question.     

Generalising a characterisation of Hermitian curves

This article proves a characterisation of the classical unital that is a generalisation of a characterisation proved in 1982 by Lefèvre-Percsy. It is shown that if is a Buekenhout-Metz unital with respect to a line in such that a line of not through meets in a Baer subline, then is classical. An immediate corollary is that if is a unital in PG such that is Buekenhout-Metz with respect to two distinct lines, then is classical. Received 5 August 1999; revised 15 February 2000.     

Reduction of Matrices over Bezout Rings of Stable Rank not Higher than 2

We prove that a commutative Bezout ring is an Hermitian ring if and only if it is a Bezout ring of stable rank 2. It is shown that a noncommutative Bezout ring of stable rank 1 is an Hermitian ring. This implies that a noncommutative semilocal Bezout ring is an Hermitian ring. We prove that the Bezout domain of stable rank 1 with two-element group of units is a ring of elementary divisors if and only if it is a duo-domain.     

Cores of convex games

The core of ann-person game is the set of feasible outcomes that cannot be improved upon by any coalition of players. A convex game is defined as one that is based on a convex set function. In this paper it is shown that the core of a convex game is not empty and that it has an especially regular structure. It is further shown that certain other cooperative solution concepts are related in a simple way to the core: The value of a convex game is the center of gravity of the extreme points of the core, and the von Neumann-Morgenstern stable set solution of a convex game is unique and coincides with the core.     

A New Definition of A Priori Knowledge: In Search of a Modal Basis

In this paper I will offer a novel understanding of a priori knowledge. My claim is that the sharp distinction that is usually made between a priori and a posteriori knowledge is groundless. It will be argued that a plausible understanding of a priori and a posteriori knowledge has to acknowledge that they are in a constant bootstrapping relationship. It is also crucial that we distinguish between a priori propositions that hold in the actual world and merely possible, non-actual a priori propositions, as we will see when considering cases like Euclidean geometry. Furthermore, contrary to what Kripke seems to suggest, a priori knowledge is intimately connected with metaphysical modality, indeed, grounded in it. The task of a priori reasoning, according to this account, is to delimit the space of metaphysically possible worlds in order for us to be able to determine what is actual.     

On uniqueness of Cartesian products of surfaces with boundary

It is known that if one of the factors of a decomposition of a manifold into Cartesian product is an interval then the decomposition is not unique. We prove that the decomposition of a 4-manifold (possibly with boundary) into 2-dimensional factors is unique, provided that the factors are not products of 1-manifolds.     

Noninjectivity of the Predual Bimodule of the Measure Algebra for Infinite Discrete Groups

In this paper, it is proved that the predual bimodule of the measure algebra of an infinite discrete group is not injective despite the fact that the measure algebra of an amenable group is amenable in the sense of Connes. Thus the well-known result of Khelemskii (claiming that, for a von Neumann algebra, Connes-amenability is equivalent to the condition that the predual bimodule is injective) cannot be extended to measure algebras. Moreover, for a discrete amenable group, we give a simple formula for a normal virtual diagonal of the measure algebra. It is shown that a certain canonical bimodule over the measure algebra is not normal.     

A posteriori joint detection of a recurring tuple of reference fragments in a quasi-periodic sequence

The problem of joint detection of a recurring tuple of reference fragments in a noisy numerical quasi-periodic sequence is solved in the framework of the a posteriori (off-line) approach. It is assumed that (i) the total number of fragments in the sequence is known, (ii) the index of the sequence member corresponding to the beginning of a fragment is a deterministic (not random) value, and (iii) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is shown that the problem consists of testing a set of simple hypotheses about the mean of a random Gaussian vector. A specific feature of the problem is that the cardinality of the set grows exponentially as the vector dimension (i.e., the length of the observed sequence) and the number of fragments in the sequence increase. It is established that the search for a maximum-likelihood hypothesis is equivalent to the search for arguments that maximize a special auxiliary objective function with linear inequality constraints. It is shown that this function is maximized by solving the basic extremum problem. It is proved that this problem is solvable in polynomial time. An exact algorithm for its solution is substantiated that underlies an algorithm guaranteeing optimal (maximum-likelihood) detection of a recurring tuple of reference fragments. The results of numerical simulation demonstrate the noise stability of the detection algorithm.     

Modules and ideals of algebras of associative type

In this paper, we study some properties of algebras of associative type introduced in previous papers of the author. We show that a finite-dimensional algebra of associative type over a field of zero characteristic is homogeneously semisimple if and only if a certain form defined by the trace form is nonsingular. For a subclass of algebras of associative type, it is proved that any module over a semisimple algebra is completely reducible. We also prove that any left homogeneous ideal of a semisimple algebra of associative type is generated by a homogeneous idempotent.     

Adjacency posets of planar graphs

In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poset has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph.     

Extension of a theorem of Whitney

It is shown that every planar graph with no separating triangles is a subgraph of a Hamiltonian planar graph; that is, Whitney’s theorem holds without the assumption of a triangulation.