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.     

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.     

Maximum genus, connectivity and minimal degree of graphs

This paper is devoted to the lower bounds on the maximum genus of graphs. A simple statement of our results in this paper can be expressed in the following form:

Let G be a k-edge-connected graph with minimum degree δ, for each positive integer k(3), there exists a non-decreasing function f(δ) such that the maximum genus γ_M(G) of G satisfies the relation γ_M(G)f(δ)β(G), and furthermore that lim_δ→∞f(δ)=1/2, where β(G)=|E(G)|-|V(G)|+1 is the cycle rank of G.

The result shows that lower bounds of the maximum genus of graphs with any given connectivity become larger and larger as their minimum degree increases, and complements recent results of several authors.     

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→∞.     

The bandwidth sum of join and composition of graphs

Given a graph G, a proper labeling f of G is a one-to-one function . The bandwidth sum of a graph G, denoted by B_s(G), is defined by B_s(G)=min∑_uvE(G)|f(u)-f(v)|, where the minimum is taken for all proper labelings f of G. In this paper, we give some results for the bandwidth sum problem for the join of k graphs G₁,G₂,…,G_k, where each G_i is a path, cycle, complete graph, or union of isolated vertices. We also discuss the bandwidth sum for the composition of two graphs G and H, where G and H are path, cycle, or union of isolated vertices.     

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₄₉.     

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 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.     

A combinatorial approach to doubly transitive permutation groups

Let G be a doubly but not triply transitive group on a set X. We give an algorithm to construct the orbits of G acting on X×X×X by combining those of its stabilizer H of a point of X If the group H is given first, we compute the orbits of its transitive extension G, if it exists. We apply our algorithm to G=PSL(m,q) and Sp(2m,2), m3, successfully. We go forward to compute the transitive extension of G itself. In our construction we use a superscheme defined by the orbits of H on X×X×X and do not use group elements.     

Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

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.     

A loop-free two-close Gray-code algorithm for listing k-ary Dyck words

P. Chase and F. Ruskey each published a Gray code for length n binary strings with m occurrences of 1, coding m-combinations of n objects, which is two-close—that is, in passing from one binary string to its successor a single 1 exchanges positions with a 0 which is either adjacent to the 1 or separated from it by a single 0. If we impose the restriction that any suffix of a string contains at least k−1 times as many 0's as 1's, we obtain k-suffixes: suffixes of k-ary Dyck words. Combinations are retrieved as special case by setting k=1 and k-ary Dyck words are retrieved as a special case by imposing the additional condition that the entire string has exactly k−1 times as many 0's as 1's. We generalize Ruskey's Gray code to the first two-close Gray code for k-suffixes and we provide a loop-free implementation for k2. For k=1 we use a simplified version of Chase's loop-free algorithm for generating his two-close Gray code for combinations. These results are optimal in the sense that there does not always exist a Gray code, either for combinations or Dyck words, in which the 1 and the 0 that exchange positions are adjacent.     

Countable choice and compactness

We work in set-theory without choice ZF. Denoting by the countable axiom of choice, we show in that the closed unit ball of a uniformly convex Banach space is compact in the convex topology (an alternative to the weak topology in ZF). We prove that this ball is (closely) convex-compact in the convex topology. Given a set I, a real number p1 (respectively p=0), and some closed subset F of [0,1]^I which is a bounded subset of ℓ^p(I), we show that (respectively DC, the axiom of Dependent Choices) implies the compactness of F.     

Chaining algorithms for multiple genome comparison

Given n fragments from k>2 genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in O(nlog^kn) time and O(nlog^k−1n) space. For gap costs in the L₁-metric, we reduce the time complexity of their algorithm by a factor and the space complexity by a factor logn. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor . A variant of our algorithm finds all significant local chains of colinear non-overlapping fragments. These chaining algorithms can be used in a variety of problems in comparative genomics: the computation of global alignments of complete genomes, the identification of regions of similarity (candidate regions of conserved synteny), the detection of genome rearrangements, and exon prediction.     

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.     

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.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics

We study the problem of finding a length-constrained maximum-density path in a tree with weight and length on each edge. This problem was proposed in [R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, Journal of Combinatorial Optimization 9 (2005) 147–156] and solved in O(nU) time when the edge lengths are positive integers, where n is the number of nodes in the tree and U is the length upper bound of the path. We present an algorithm that runs in O(nlog²n) time for the generalized case when the edge lengths are positive real numbers, which indicates an improvement when U=Ω(log²n). The complexity is reduced to O(nlogn) when edge lengths are uniform. In addition, we study the generalized problems of finding a length-constrained maximum-sum or maximum-density subtree in a given tree or graph, providing algorithmic and complexity results.     

Discrete subspaces of countably tight compacta

Our main result is that the following cardinal arithmetic assumption, which is a slight weakening of GCH, “2^κ is a finite successor of κ for every cardinal κ”, implies that in any countably tight compactum X there is a discrete subspace D with . This yields a (consistent) confirmation of Alan Dow’s Conjecture 2 from [A. Dow, Closures of discrete sets in compact spaces, Studia Math. Sci. Hung. 42 (2005) 227–234].     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.