Limit shape of convex lattice polygons with minimal perimeter

Let n be a positive integer and · any norm in . Denote by B the unit ball of · and the class of convex lattice polygons with n vertices and least ·-perimeter. We prove that after suitable normalization, all members of tend to a fixed convex body, as n→∞.     

Generalizing the Quinn–Wójs theorem on distinct multiplets of composite Fermions

The combinatorial tool of generating functions for restricted partitions is used to generalize a quantum physics theorem relating distinct multiplets of different angular momenta in the composite Fermion model of the fractional quantum Hall effect. Specifically, if g_ℓ(N,M) denotes the number of distinct multiplets of angular momentum ℓ and total angular momentum M, we prove that

where the sum is taken over all positive divisors of N and L(k)=kℓ-kN/2+3k/2-N+N/(2k)-1/2. The original Quinn–Wójs theorem results when k=1 and it appears that this generalization will be useful in further investigations of nuclear shells modeling elementary particle interactions when the particles are clustered together.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

A note on 2-factors with two components

In this note, we consider a minimum degree condition for a hamiltonian graph to have a 2-factor with two components. Let G be a graph of order n3. Dirac's theorem says that if the minimum degree of G is at least , then G has a hamiltonian cycle. Furthermore, Brandt et al. [J. Graph Theory 24 (1997) 165–173] proved that if n8, then G has a 2-factor with two components. Both theorems are sharp and there are infinitely many graphs G of odd order and minimum degree which have no 2-factor. However, if hamiltonicity is assumed, we can relax the minimum degree condition for the existence of a 2-factor with two components. We prove in this note that a hamiltonian graph of order n6 and minimum degree at least has a 2-factor with two components.     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.     

On distinct unit fractions whose sum equals 1

Questions, partial and complete answers about the diophantine equation in distinct positive integers are given when additional requirements are asked on the x_i's such as: being large, odd, even or x_ix_j for i≠j. Various combinations of the above conditions are also considered.     

Mass formula for self-dual codes over Z

We give a mass formula for self-dual codes over Z_p², where p is an odd prime. Using the mass formula, we classify such codes of lengths up to n=8 over the ring Z₉, n=7 over Z₂₅ and n=6 over Z₄₉.     

Nonexistence of a code for

In this paper, we shall prove that there is no [3q⁴-q³-q²-3q-1,5,3q⁴-4q³-2q+1]_q code over the finite field for q11. Thus, we conclude the nonexistence of a [g_q(5,d),5,d]_q code for 3q⁴-4q³-2q+1d3q⁴-4q³-q.     

Space-efficient geometric divide-and-conquer algorithms

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in time using extra memory given inputs of size n for the closest pair problem and a randomized solution running in expected time and using extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in time using extra space where n is the number of horizontal and vertical line segments and k is the number of intersections.     

Maximal realcompact spaces and measurable cardinals

Comfort and Hager investigate the notion of a maximal realcompact space and ask about the relationship to the first measurable cardinal . A space is said to be a space if the intersection of fewer than open sets is again open. They ask if each realcompact space is maximal realcompact. We establish that this question is undecidable.     

Minimum weight pseudo-triangulations

We consider the problem of computing a minimum weight pseudo-triangulation of a set of n points in the plane. We first present an -time algorithm that produces a pseudo-triangulation of weight which is shown to be asymptotically worst-case optimal, i.e., there exists a point set for which every pseudo-triangulation has weight , where is the weight of a minimum weight spanning tree of . We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.     

The number of translates of a closed nowhere dense set required to cover a Polish group

For a Polish group let be the minimal number of translates of a fixed closed nowhere dense subset of required to cover . For many locally compact this cardinal is known to be consistently larger than which is the smallest cardinality of a covering of the real line by meagre sets. It is shown that for several non-locally compact groups . For example the equality holds for the group of permutations of the integers, the additive group of a separable Banach space with an unconditional basis and the group of homeomorphisms of various compact spaces.     

Nonlinear maps preserving Lie products on factor von Neumann algebras

In this paper, we prove that every bijective map preserving Lie products from a factor von Neumann algebra into another factor von Neumann algebra is of the form A→ψ(A)+ξ(A), where is an additive isomorphism or the negative of an additive anti-isomorphism and is a map with ξ(AB-BA)=0 for all .     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].     

Eigenvalues of association schemes of quadratic forms

The duality and primitivity of the association scheme Qua(n,q) of quadratic forms in n variables and the association scheme Sym(n,q) of symmetric bilinear forms in n variables over the finite field are discussed by Wang et al. [Association schemes of quadratic forms and symmetric bilinear forms, J. Algebraic Combin. 17 (2003) 149–161]. In this paper, eigenvalues of Qua(n,q) are computed, where q is a power of 2. As an application, two fusion schemes of Qua(n,q) are discussed and their dual schemes are constructed.     

On the stability and boundedness of solutions of a kind of third order delay differential equations

In this paper, we study Eq. (1.1) for asymptotic stability of the zero solution when and uniformly bounded and uniformly ultimate bounded of all solutions when      

On four color monochromatic sets with nondecreasing diameter

Let m and r be positive integers. Define f(m,r) to be the least positive integer N such that for every coloring of the integers 1,…,N with r colors there exist monochromatic subsets B₁ and B₂ (not necessarily of the same color), each having m elements, such that (a) max(B₁)-min(B₁)max(B₂)-min(B₂), and (b) max(B₁)B₂). We improve previous upper bounds to determine that f(m,4)=12m-9.     

On periodic radical groups in which permutability is a transitive relation

A group G is said to be a -group if permutability is a transitive relation in the set of all subgroups of G. Our purpose in this paper is to study -groups in the class of periodic radical groups satisfying min-p for all primes p.     

Characterizations of maximum matching graphs of certain types

The maximum matching graph of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.