The generalized column incidence graph and a matroid base-listing algorithm

The generalized column incidence graph of a matroid base is defined, and it is shown that all elements on a minimal path in this graph lie in a common circuit. Also, an algorithm is provided which lists all bases of a matroid and calculates the Whitney and Tutte polynomials. The complexity of this algorithm is shown to be O(mN(n- m)(c(M) + m)), where Mis a matroid of rank mon a set of cardinality nNis the number of bases of M, and c(M) is the complexity of checking independence in M.     

On Mills's conjecture on matroids with many common bases

In this paper, we shall prove a conjecture of Mills: for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n₁ circuit-hyperplanes and from the other by relaxing n₂ circuit-hyperplanes, where n₁ and n₂ are non-negative integers such that n₁+n₂k     

Popular distances in 3-space

Let m(n) denote the smallest integer m with the property that any set of n points in Euclidean 3-space has an element such that at most m other elements are equidistant from it. We have that cn^1/3 log log n m(n) n^3/5 β(n), where c> 0 is a constant and β(n) is an extremely slowly growing function, related to the inverse of the Ackermann function.     

Incidence matrices, geometrical bases, combinatorial prebases and matroids

For a relation A (C × D), where C,D are two finite sets, and an ordering σ of C we construct a matroid M(σ) on the set D. For the relation A with the incidence matrix  we also define a geometrical basis with respect to F, where F is a subset of the set of all circuits of the column matroid on Â. Geometrical bases are certain bases of this column matroid. We establish connections between the bases of matroids M(σ) and the geometrical bases of A with respect to F. These connections give a combinatorial way of constructing bases of the column matroid on  using a subset F of its circuits.

We also consider a matroid M and the incidence relation between what we call the extended circuits of M and the bases of M. Applying the technique above we obtain the matroids M(σ) on the set of bases of the matroid M. In case of the incidence relation between vertices and edges of a graph this technique yields a unique matroid, the usual matroid of the graph.

Some particular relations are considered: a class of relations with a certain property (the T-property) and the relation of inclusion of chambers in simplices in an affine point configuration.     

Sperner''s theorem with constraints

A set X of subsets of an n-element set S is called an anti-chain if no two elements of X are related by set-wise inclusion. Sperner showed [8] that max |X|=(ⁿ_[n/2]), where |X| denotes the number of elements in X and the maximum is taken over all anti-chains of subsets of S.

Let non-negative integers i_o<n and m_io≠0, m_io+1,…m_n be given. In this paper we give an algorithm for calculating max |X| where the maximum is taken only over anti-chains containing exactly m_i i-element subsets of S for i_o i n.     

Matroids with many common bases

Lemos (Discrete Math. 240 (2001) 271–276) proved a conjecture of Mills (Discrete Math. 203 (1999) 195–205): for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n₁ circuit-hyperplanes and from the other by relaxing n₂ circuit-hyperplanes, where n₁ and n₂ are non-negative integers such that n₁+n₂k. In this paper, we prove a similar result, where the hypothesis of the matroids being k-connected is replaced by the weaker hypothesis of being vertically k-connected.     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O（n^k+2/（k-1）!）.同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O（（2n+m+n log n）n^k-1/（k-1）!）.     

A generalized Desargues configuration and the pure braid group

In this paper, a configuration with n = (₂^d) points in the plane is described. This configuration, as a matroid, is a Desargues configuration if d = 5, and the union of (₅^d) such configurations if d> 5. As an oriented matroid, it is a rank 3 truncation of the directed complete graph on d vertices. From this fact, it follows from a version of the Lefschetz-Zariski theorem implied by results of Salvetti that the fundamental group π of the complexification of its line arrangement is Artin's pure (or coloured) braid group on d strands.

In this paper we obtain, by using techniques introduced by Salvetti, a new algorithm for finding a presentation of π based on this particular configuration.     

Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Regular expression searching on compressed text

We present a solution to the problem of regular expression searching on compressed text. The format we choose is the Ziv–Lempel family, specifically the LZ78 and LZW variants. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text in O(2^m+mn+Rmlogm) worst case time. On average this drops to O(m²+(n+Rm)logm) or O(m²+n+Ru/n) for most regular expressions. This is the first nontrivial result for this problem. The experimental results show that our compressed search algorithm needs half the time necessary for decompression plus searching, which is currently the only alternative.     

Multicolor Combination Lemma

We present an extension of the Combination Lemma of Guibas et al. (1983) that expresses the complexity of one or several faces in the overlay of many arrangements (as opposed to just two arrangements in (Guibas et al. 1989)), as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applications of the new Combination Lemma are presented. We first show that the complexity of a single face in an arrangement of k simple polygons with a total of n sides is Θ(n(k)), where (·) is the inverse of Ackermann's function. We also give a new and simpler proof of the bound on the total number of edges of m faces in an arrangement of n Jordan arcs, each pair of which intersect in at most s points, where λ_s(n) is the maximum length of a Davenport–Schinzel sequence of order s with n symbols. We extend this result, showing that the total number of edges of m faces in a sparse arrangement of n Jordan arcs is , where w is the total complexity of the arrangement. Several other related results are also obtained.     

Strong Laws of Large Numbers for Double Sums of Banach Space Valued Random Elements

For a double array {V_(m,n), m ≥ 1, n ≥ 1} of independent, mean 0 random elements in a real separable Rademacher type p(1 ≤ p ≤ 2) Banach space and an increasing double array {b_(m,n), m ≥1, n ≥ 1} of positive constants, the limit law ■ and in L_p as m∨n→∞ is shown to hold if ■ This strong law of large numbers provides a complete characterization of Rademacher type p Banach spaces. Results of this form are also established when 0 p ≤ 1 where no independence or mean 0 conditions are placed on the random elements and without any geometric conditions placed on the underlying Banach space.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

Computing the face lattice of a polytope from its vertex-facet incidences

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(min{n,m}··), where n is the number of vertices, m is the number of facets, is the number of vertex-facet incidences, and  is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191–198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·²) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d··). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.     

L2-approximation of real-valued functions with interpolatory constraints

We construct the polynomial p_m,n^* of degree m which interpolates a given real-valued function f L²[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L₂-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L₂-error p_m,n^* − f → 0 as m → ∞ if f C[a, b].     

Further results on irregular, critical perfect systems of difference sets II: systems without splits

An (m, n; u, v; c)-system is a collection of components, m of valency u−1 and n of valency v−1, whose difference sets form a perfect system with threshold c. If there is an (m, n; 3, 6; c)-system, then m2c−1; and if there is a (2c−1, n; 3, 6; c)-system, then 2c−1n. For all sufficiently large c, there are (2c−1, n; 3, 6; c)-systems with a split at 3c+6n−1 at least when n=1, 5, 6 and 7, but such systems do not exist for n=2, 3 or 4.

We describe here a general method of construction for (2c−1, n; 3, 6; c)-systems and use it to show that there are such systems for 2n4 and certain values of c depending on n. We also discuss the limitations of this method.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.