On simple and supersimple transversal designs

In this paper, the existence of a transversal design TD_λ (4, g) is proved for all indices λ satisfying 2 ≤ λ ≤ g such that any two of its blocks intersect in at most two elements. Similar results are obtained for transversal designs without repeated blocks. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 311–320, 2000     

Lower Bounds for Transversal Covers

A transversal cover is a set of gk points in k disjoint groups of size g and a collection of b transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. A central question is to determine, for given g, the minimum possible b for fixed k, or, alternatively, the maximum k for fixed b. The case g=2 was investigated and completely solved by Sperner sperner:28, Rényi renyi:71, Katona katona:73, and Kleitman and Spencer kleitman:73. For arbitrary g, asymptotic results are known but little is understood for small values of k. Constructions exist but these only produce upper bounds on b. The present article is concerned with lower bounds on b. We develop three general lower bounds on b for fixedg and k. The first one is proved using one of the principal constructions brett:97a, the second comes from the study of intersecting set-systems, and the third is shown by a set packing argument. In addition, we investigate upper bounds on k for small fixed b. This proves useful to reduce or eliminate the gap between lower and upper bounds on b for some transversal covers with small k.     

Line Transversals in Large <Emphasis Type="Italic">T</Emphasis>(3)- and <Emphasis Type="Italic">T</Emphasis>(4)-Families of Congruent Discs

A family of closed discs is said to have property T(k) if to every subset of at most k discs there belongs a common line transversal. A family of discs is said to be d-disjoint, d≥1, if the mutual distance between the centers of the discs is larger than d. It is known that a d-disjoint T(3)-family ℱ of unit diameter discs has a line transversal if . Similarly, a d-disjoint T(4)-family has a line transversal if . Both results are sharp in d, i.e., they do not hold for smaller values of d. The main result of this paper is that while the above lower bounds on d cannot be relaxed in general, some reduction of d can be compensated by imposing a proper d-dependent lower bound on the size of the family in both cases.     

Group construction of covering arrays

A covering array t‐CA (n, k, g) is a k × n array on a set of g symbols with the property that in each t × n subarray, every t × 1 column appears at least once. This paper improves many of the best known upper bounds on n for covering arrays, 2‐CA (n, k, g) with g + 1 ≤ k ≤ 2g, for g = 3 · · · 12 by a construction which in many of these cases produces a 2‐CA (n, k, g) with n = k (g ? 1) + 1. The construction is an extension of an algebraic method used by Chateauneuf, Colbourn, and Kreher which uses an array and a group action on the array. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 70–77, 2005.     

A unified approach to known and unknown cases of Berge's conjecture

Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition P of the vertex set of a digraph minimizing , there exists a collection C^k of k disjoint independent sets, where each dipath P∈P meets exactly min{|P|, k} of the independent sets in C. This conjecture extends Linial's conjecture, the Greene–Kleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for acyclic digraphs. For general digraphs, it is known for k=1 by the Gallai–Milgram Theorem, for k?λ (where λis the number of vertices in the longest dipath in the graph), by the Gallai–Roy Theorem, and when the optimal path partition P contains only dipaths P with |P|?k. Recently, it was proved (Eur J Combin (2007)) for k=2. There was no proof that covers all the known cases of Berge's conjecture. In this article, we give an algorithmic proof of a stronger version of the conjecture for acyclic digraphs, using network flows, which covers all the known cases, except the case k=2, and the new, unknown case, of k=λ?1 for all digraphs. So far, there has been no proof that unified all these cases. This proof gives hope for finding a proof for all k.     

Bachelor latin squares with large indivisible plexes

In a latin square of order n , a k ‐plex is a selection of kn entries in which each row, column, and symbol occurs k times. A 1 ‐plex is also called a transversal. A k ‐plex is indivisible if it contains no c ‐plex for 0 < c < k . We prove that, for all n ≥ 4 , there exists a latin square of order n that can be partitioned into an indivisible ? n / 2 ?‐plex and a disjoint indivisible ? n / 2 ?‐plex. For all n ≥ 3 , we prove that there exists a latin square of order n with two disjoint indivisible ? n / 2 ?‐plexes. We also give a short new proof that, for all odd n ≥ 5 , there exists a latin square of order n with at least one entry not in any transversal. Such latin squares have no orthogonal mate. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:304‐312, 2011     

Latin squares with no small odd plexes

A k‐plex in a Latin square of order n is a selection of kn entries in which each row, column, and symbol is represented precisely k times. A transversal of a Latin square corresponds to the case k = 1. We show that for all even n > 2 there exists a Latin square of order n which has no k‐plex for any odd but does have a k‐plex for every other . © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 477–492, 2008     

Modified generalized Hadamard matrices and constructions for transversal designs

It is well known that there exists a transversal design TD_λ[k; u] admitting a class regular automorphism group U if and only if there exists a generalized Hadamard matrix GH(u, λ) over U. Note that in this case the resulting transversal design is symmetric by Jungnickel’s result. In this article we define a modified generalized Hadamard matrix and show that transversal designs which are not necessarily symmetric can be constructed from these under a modified condition similar to class regularity even if it admits no class regular automorphism group.     

The transversal homoclinic points are dense in the codimension-1 Hénon-like strange attractors

We consider the codimension-1 Hénon-like strange attractors . We prove that the transversal homoclinic points are dense in , and that hyperbolic periodic points are dense in . Moreover the hyperbolic periodic points that are heteroclinically related to the primary fixed point ( transversal intersection of stable and unstable manifolds) are dense in .

     

Halving transversal designs

A factor H of a transversal design TD(k,n) = (V,𝒢, ℬ︁), where V is the set of points, 𝒢 the set of groups of size n and ℬ︁ the set of blocks of size k, is a triple (V,𝒢, 𝒟) such that 𝒟 is a subset of ℬ︁. A halving of a TD (k, n) is a pair of factors H_i = (V, 𝒢, 𝒟_i), i = 1,2 such that 𝒟₁ ∪ 𝒟₂ = ℬ︁, 𝒟₁ ∩ 𝒟₂ = ∅︁ and H₁ is isomorphic to H₂. A path of length q is a sequence x₀, x₁,…,x_q of points such that for each i = 1, 2,…, q the points x_i‐1 and x_i belong to a block B_i and no point appears more than once. The distance between points x and y in a factor H is the length of the shortest path from x to y. The diameter of a connected factor H is the maximum of the set of distances among all pairs of points of H. We prove that a TD (3, n) is halvable into isomorphic factors of diameter d only if d = 2,3,4, or ∞ and we completely determine for which values of n there exists such a halvable TD (3, n). We also show that if any group divisible design with block size at least 3 is decomposed into two factors with the same finite diameter d, then d≤ 4. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 83–99, 2000     

Finding odd cycle transversals

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.     

Extremal Regular Graphs with Prescribed Odd Girth

The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ƒ(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ƒ(k, g) ≥ kg/2 and that ƒ(k, g) = kg/2 if k is even. The exact values of ƒ(k, g) are also known if k = 3 or g = 5. Let x_e denote the smallest even integer no less than x, δ(g) = (−1)^{g − 1}/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ≥ 5 and g ≥ 7 are both odd, then [formula] with the exception that ƒ(5, 7) = 20.     

Small Uniformly Resolvable Designs for Block Sizes 3 and 4

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k‐pc and for a given k the number of k‐pcs is denoted r_k. In this paper, we consider the case of block sizes 3 and 4 (both existent). We use v to denote the number of points, in this case the necessary conditions imply that v ≡ 0 (mod 12). We prove that all admissible URDs with v < 200 points exist, with the possible exceptions of 13 values of r₄ over all permissible v. We obtain a URD({3, 4}; 276) with r₄ = 9 by direct construction use it to and complete the construction of all URD({3, 4}; v) with r₄ = 9. We prove that all admissible URDs for v ≡ 36 (mod 144), v ≡ 0 (mod 60), v ≡ 36 (mod 108), and v ≡ 24 (mod 48) exist, with a few possible exceptions. Recently, the existence of URDs for all admissible parameter sets with v ≡ 0 (mod 48) was settled, this together with the latter result gives the existence all admissible URDs for v ≡ 0 (mod 24), with a few possible exceptions.     

More on an Erdős–Szekeres-Type Problem for Interior Points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k≥1, let g(k) be the smallest integer such that every planar point set in general position with at least g(k) interior points has a convex subset of points with exactly k interior points of P. In this article, we prove that g(3)=9.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

The Nielsen number for free fundamental groups and maps without remnant

For Y any space that has the homotopy type of a wedge of finitely many circles, and for g : Y → Y a map, the Nielsen number of g, N(g), is a homotopy invariant lower bound for the size of the fixed point set of any map homotopic to g. Such a map g has k-remnant if, roughly, there is limited cancellation in any product g _♯(u)g _♯(v) where g _♯ is the induced homomorphism and u, v ∈ π₁(Y) and |u| = |v| = k. We prove that such maps are (k + 1)-characteristic, meaning that in order to determine the Nielsen classes of fixed points, we need only test whether a limited, specified, set of elements z ∈ π₁(Y) are solutions to the equation z = W ⁻¹ _x f _♯(z)W _y , with x and y fixed points that are represented in the fundamental group by W _x and W _y , respectively. The number of elements to be tested is profoundly decreased by using abelianization as well. This work is a significant extension of Wagner’s results involving maps with remnant and Wagner’s algorithm. Our proofs involve new concepts and techniques. We present an algorithm for N(g) for any map g with k-remnant, and we provide examples for which no algebraic techniques previously known would work. One example shows that for any k there is a map that does not have (k − 1)-remnant but does have k-remnant. Dedicated to Edward Fadell for inspirational teaching and guidance as the thesis advisor of the first author     

Packing Arrays and Packing Designs

A packing array is a b × k array, A with entriesa _i,j from a g-ary alphabet such that given any two columns,i and j, and for all ordered pairs of elements from a g-ary alphabet,(g ₁, g ₂), there is at most one row, r, such thata _r,i = g ₁ anda _r,j = g ₂. Further, there is a set of at leastn rows that pairwise differ in each column: they are disjoint. A central question is to determine, forgiven g, k and n, the maximum possible b. We examine the implications whenn is close to g. We give a brief analysis of the case n = g and showthat 2g rows is always achievable whenever more than g exist. We give an upper bound derivedfrom design packing numbers when n = g – 1. When g + 1 k then this bound is always at least as good as the modified Plotkin bound of [12]. When theassociated packing has as many points as blocks and has reasonably uniform replication numbers, we show thatthis bound is tight. In particular, finite geometries imply the existence of a family of optimal or near optimalpacking arrays. When no projective plane exists we present similarly strong results. This article completelydetermines the packing numbers, D(v, k, 1), when .     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

On Inverse Transversals of Ordered Regular Semigroups

We first consider an ordered regular semigroup S in which every element has a biggest inverse and determine necessary and sufficient conditions for the subset S ^○ of biggest inverses to be an inverse transversal of S. Such an inverse transversal is necessarily weakly multiplicative. We then investigate principally ordered regular semigroups S with the property that S ^○ is an inverse transversal. In such a semigroup we determine precisely when the set S ^☆ of biggest pre-inverses is a subsemigroup and show that in this case S ^☆ is itself an inverse transversal of a subsemigroup of S. The ordered regular semigroup of 2 × 2 boolean matrices provides an informative illustrative example. The structure of S, when S ^☆ is a group, is also described.     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007