The intersection problem for m-cycle systems

Let I_m(v) denote the set of integers k for which a pair of m-cycle systems of K_v, exist, on the same vertex set, having k common cycles. Let J_m(v) = {0, 1, 2,…, t_v ?2, t_v} where t_v = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when I_m(2mn + x) = J_m(2mn + x), for both m even and m odd. Results include J^m(2mn + 1) = I^m(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K_2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc.     

Parallel Dixon Matrices by Bracket

It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)²(m+2)n(n+1)²(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct.     

The Smirnov distribution

Summary Adequacy of the Smirnov approximation to P (D _mn ≧c/mn), of the exact distribution of the two sample Kolmogorov-Smirnov criterion,D _mn ,m<=n is examined. The main finding is that accuracy depends as much on the sample sizes,m andn, as on the ratio, ρ=m/n. The Smirnov approximation is good whenn is an integer multiple ofm, especiallyn=m, 2m; poor otherwise. This contrasts with the Smirnov approximation to P (D _mn >c/mn), where this ordering is reversed, the cases forn=m, 2m being poor. The merit of continuity correction, of order ofn ⁻¹ in theD _mn scale, is demonstrated for the Smirnov approximation, .1≦ρ, as well as for the Kolmogorov approximation, ρ<.1. As an argument for the optimum choice of ρ, the casen=m+1 is shown to have much to recommend it over the casen=m. Finally the usefulness of theχ ² distribution with 2 degress of freedom is illustrated as an approximation to the Smirnov distribution. This study was in part supported by USPHS-NIH Grant number 2 DO4 AH 0167 07 PHT Development Project.     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Embedding directed and undirected partial cycle systems of index λ > 1

Recent results have found small embeddings for partial m-cycle systems of order n with λ= 1. However, if λ> 1 then the best known techniques produce embeddings that are often quadratic functions of both m and n and linear functions of λ. In this article we obtain embeddings for partial m-cycle systems of order n, and of partial directed m-cycle systems, for all values of m. These embeddings are independent of λ and linear in both n and m. © 1993 John Wiley & Sons, Inc.     

Embedding Partial 4-cycle Systems of Arbitrary Index

Recently, Lindner showed that every partial 4-cycle system of order n and index 1 could be embedded in a 4-cycle system of order ν and index 1 with v ≤ 2n + 15. While the technique he used does not immediately extend to any higher index, here we develop his ideas to show that every partial 4-cycle system of order n and index λ can be embedded in a 4-cycle system of order v and index λ for all λ-admissible . This improves on the best known bounds of v = 4n and v = 8n + 1 when λ > 1 is even and odd respectively.     

On equationally defining m-perfect 2m + 1 cycle systems

In this article we give a complete solution to the problem of equationally defining m-perfect (2m + 1)-cycle systems and of equationally defining m-perfect directed (2m + 1)-cycle systems. © 1994 John Wiley & Sons, Inc.     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

On 4-cycles in random bipartite tournaments

We consider a random m by n bipartite tournament T_mn consisting of mn independent random arcs which have a common probability p of being directed from the m part to the n part. We determine the expected value and variance of the number of 4-cycles in T_mn and the probability that T_mn has no cycles. An asymptotic expression for this probability is also given when p = 1/2 and m and n tend to infinity.     

P 3-factorization of complete multipartite graphs

In this note it is shown that a necessary and sufficient condition for the existence of a P3-factorizatlon of complete multipartite graph λK, is (1) m≥3, (2) mn≡0(mod 3) and (3)λ(m-1)n≡0(mod 4).     

Algorithms for shortest paths and d-cycle problems

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n²m) and O(n^2d−1m²) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^2d−1+n²m+n³logn).     

On powerful distributional tests based on sample spacings

This paper is devoted to tests for uniformity based on sum-functions of m-spacings, where m diverges to infinity as the sample size, n, increases. It is shown that if m diverges at a slower rate than n^1/2 then the commonly used sum-function will detect alternatives distant (mn)^−1/4 from the uniform. This result fails if m diverges more quickly than n^1/2, and in that situation the statistic must be modified. The case where m/n → , 0 < < 1, is also considered, and it is shown that the test has adequate power against local and fixed alternatives if and only if is irrational.     

Fibonacci and Lucas congruences and their applications

In this paper we obtain some new identities containing Fibonacci and Lucas numbers. These identities allow us to give some congruences concerning Fibonacci and Lucas numbers such as L _2mn+k ≡ (−1)^(m+1)n L _k (mod L _m ), F _2mn+k ≡ (−1)^(m+1)n F _k (mod L _m ), L _2mn+k ≡ (−1) ^mn L _k (mod F _m ) and F _2mn+k ≡ (−1) ^mn F _k (mod F _m ). By the achieved identities, divisibility properties of Fibonacci and Lucas numbers are given. Then it is proved that there is no Lucas number L _n such that L _n = L ₂ ^k t L _m x ² for m > 1 and k ≥ 1. Moreover it is proved that L _n = L _m L _r is impossible if m and r are positive integers greater than 1. Also, a conjecture concerning with the subject is given.     

Convergence of ray sequences of Padé approximants for 2 f 1(a, 1; c; z), (c > a > 0)

The Padé table of ₂ F ₁(a, 1; c; z) is normal for c > a > 0 (cf. [4]). For m ≥ n - 1 and c ? Z^-, the denominator polynomial Q _mn (z) in the [m/n] Padé approximant P _mn (z)/Q _mn (z) for ₂ F ₁(a, 1; c; z) and the remainder term Q _mn (z)₂ F ₁(a, 1; c; z)-P_mn (z) were explicitly evaluated by Padé (cf. [2], [6] or [9]). We show that for c > a > 0 and m ≥ n - 1, the poles of P_mn (z)/Q_mn (z) lie on the cut (1,∞). We deduce that the sequence of approximants P_mn (z)/Q_mn (z) converges to ₂ F ₁(a, 1; c; z) as m → ∞, n/m → ρ with 0 < ρ ≤ 1, uniformly on compact subsets of the unit disc |z| < 1 for c > a > 0.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

Regular<Emphasis Type="Italic">n</Emphasis>-simplices in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> with vertices in ℤ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper theI andII regularn-simplices are introduced. We prove that the sufficient and necessary conditions for existence of anI regularn-simplex in ℝ ⁿ are that ifn is even thenn = 4m(m + 1), and ifn is odd thenn = 4m + 1 with thatn + 1 can be expressed as a sum of two integral squares orn = 4m - 1, and that the sufficient and necessary condition for existence of aII regularn-simplex in ℝ ⁿ isn = 2m ² - 1 orn = 4m(m + 1)(m ∈ ℕ). The connection between regularn-simplex in ℝ ⁿ and combinational design is given.     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

The braid group B4 is linear

We study a linear representation ρ:B _n ? GL _m (Z[q ^±1,t ^±1]) with m=n(n-1)/2. We will show that for n=4, this representation is faithful. We prove a relation with the new Charney length function. We formulate a conjecture implying that ρ is faithful for all n. Oblatum 15-VI-1999 & 24-II-2000?Published online: 18 September 2000     

Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs

Consider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is O(n²\frac(1+logm)m)O(n^{2}\frac{(1+\log m)}{m}) . The best previous algorithm for this problem has complexity O(mn ³) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.     

On the construction of odd cycle systems

Three obvious necessary conditions for the existence of a k-cycle system of order n are that if n > 1 then n ? k, n is odd, and 2k divides n(n ? 1). We show that if these necessary conditions are sufficient for all n satisfying k ? n < 3k then they are sufficient for all n. In particular, there exists a 15-cycle system of order n if and only if n ≡ 1, 15, 21, or 25 (mod 30), and there exists a 21-cycle system of order n if and only if n ≡ 1, 7, 15, or 21 (mod 42), n ≠ 7. 15.