Allowable Interval Sequences and Line Transversals in the Plane

Given a family F of n pairwise disjoint compact convex sets in the plane with non-empty interiors, let T(k) denote the property that every subfamily of F of size k has a line transversal, and T the property that the entire family has a line transversal. We illustrate the applicability of allowable interval sequences to problems involving line transversals in the plane by proving two new results and generalizing three old ones. Two of the old results are Klee??s assertion that if F is totally separated then T(3) implies T, and the following variation of Hadwiger??s Transversal Theorem proved by Wenger and (independently) Tverberg: If F is ordered and each four sets of F have some transversal which respects the order on F, then there is a transversal for all of F which respects this order. The third old result (a consequence of an observation made by Kramer) and the first of the new results (which partially settles a 2008 conjecture of Eckhoff) deal with fractional transversals and share the following general form: If F has property T(k) and meets certain other conditions, then there exists a transversal of some m sets in F, with k<m<n. The second new result establishes a link between transversal properties and separation properties of certain families of convex sets.     

Common transversals

Given t families, each family consisting of s finite sets, we show that if the families “separate points” in a natural way, and if the union of all the sets in all the families contains more than (s + 1)^t ? s^t?1 ? 1 elements, then a common transversal of the t families exists. In case each family is a covering family, the bound is s^t ? s^t?1. Both of these bounds are best possible. This work extends recent work of Longyear [2].     

The density of the transversal homoclinic points in the Henon-like strange attractors

We consider the Henon-like strange attractors Λ in a family which is a nonsingular perturbation of a d-modal family. The existence of the Henon-like strange attractors in this family was proved by Diaz et al. [Inventions Math. 125 (1996) 37]. 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 periodic point (transversal intersection of stable and unstable manifolds) are dense in Λ.     

Transversal wave maps and transversal exponential wave maps

Transversal wave maps and wave maps are different. There are wave maps which are not transversal wave maps, and vice versa. However, if f is a wave map under certain circumstance, then f is a transversal wave map. We show that if f is a transversal exponential wave map, then the associated energy–momentum is transversally conserved. We finally obtain the relationship among transversal wave maps, transversal exponential wave maps and certain second order symmetric tensors.     

A characterization of transversal topologies

K. Steffens (“Injektive Auswahlfunktionen,” Schriften aus dem Gebiet der Angewandten Mathematik Nr. 2, Aachen, 1972) has shown that a family of finite sets has a transversal if and only if the collection of all “critical” subfamilies forms a topology. In this paper these “transversal topologies” are characterized, as well as families whose transversal topologies satisfy separation axioms.     

Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

Associativity in multiary quasigroups: the way of biased expansions

A multiary (polyadic, n-ary) quasigroup is an n-ary operation which is invertible with respect to each of its variables. A biased expansion of a graph is a kind of branched covering graph with an additional structure similar to the combinatorial homotopy of circles. A biased expansion of a circle with chords encodes a multiary quasigroup, the chords corresponding to factorizations, i.e., associative structure. Some but not all biased expansions are constructed from groups (group expansions); these include all biased expansions of complete graphs (with at least four nodes), which correspond to Dowling’s lattices of a group and encode an iterated group operation. We show that any biased expansion of a 3-connected graph (with at least four nodes) is a group expansion, and that all 2-connected biased expansions are constructed by the identification of edges from group expansions and irreducible multiary quasigroups. If a 2-connected biased expansion covers every base edge at most three times, or if every four-node minor that contains a fixed edge is a group expansion, then the whole biased expansion is a group expansion. We deduce that if a multiary quasigroup has a factorization graph that is 3-connected, or if every ternary principal retract is an iterated group isotope, it is isotopic to an iterated group. We mention applications of generalizing Dowling geometries and of transversal designs of high strength.     

Forbidden Families of Geometric Permutations in ℝd

A geometric permutation induced by a transversal line of a finite family ℱ of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. We prove that for each natural k, each family of k permutations is realizable (as a family of geometric permutations of some ℱ) in ℝ^d for d ≥ 2k – 1, but there is a family of k permutations which is non-realizable in ℝ^d for d ≤ 2k – 2.     

Line Transversals to Unit Disks

Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

Line Transversals to Unit Disks

   Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

A colorful theorem on transversal lines to plane convex sets

We prove a colorful version of Hadwiger’s transversal line theorem: if a family of colored and numbered convex sets in the plane has the property that any three differently colored members have a transversal line that meet the sets consistently with the numbering, then there exists a color such that all the convex sets of that color have a transversal line. All authors are partially supported by CONACYT research grant 5040017.     

On the transversal Helly numbers of disjoint and overlapping disks

A family of disks is said to have the property T(k) if any k members of the family have a common line transversal. We call a family of unit diameter disks t-disjoint if the distances between the centers are greater than t. We consider for each natural number k≧ 3 the infimum t_k of the distances t for which any finite family of t-disjoint unit diameter disks with the property T(k) has a line transversal. We determine exact values of t₃ and t₄, and give general lower and upper bounds on the sequence t_k, showing that t_k = O(1/k) as k → ∞. In honour of Helge Tverberg’s seventieth birthday Received: 9 June 2005     

Truncations of principal geometries

We investigate the class of principal pregeometries (free simplicial geometries with spanning simplex) which form an important subclass of the class of transversal pregeometries (free simplicial geometries). We give a coordinate-free method for imbedding a transversal pregeometry on a simplex as a free simplicial pregeometry which makes use only of the set-theoretic properties of a presentation of the transversal pregeometry. We introduce the notion of an (r, k)-principal set as a generalization of principal basis and prove the collection of (r, k)-principal sets of a rank k pregeometry, if non-empty, are the bases of another pregeometry whose structure is determined. An algorithm for constructing principal sets is given. We then characterize truncations of principal geometries in terms of the existence of a principal set. We do this by erecting a given pregeometry to a free simplicial pregeometry with spanning simplex. The erection is the freest of all erections of the given pregeometry.     

The colored Hadwiger transversal theorem in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

Hadwiger’s transversal theorem gives necessary and suffcient conditions for a family of convex sets in the plane to have a line transversal. A higher dimensional version was obtained by Goodman, Pollack and Wenger, and recently a colorful version appeared due to Arocha, Bracho and Montejano. We show that it is possible to combine both results to obtain a colored version of Hadwiger's theorem in higher dimensions. The proofs differ from the previous ones and use a variant of the Borsuk-Ulam theorem. To be precise, we prove the following. Let F be a family of convex sets in ? ^d in bijection with a set P of points in ? ^d?1. Assume that there is a coloring of F with suffciently many colors such that any colorful Radon partition of points in P corresponds to a colorful Radon partition of sets in F. Then some monochromatic subfamily of F has a hyperplane transversal.     

A gallai-type transversal problem in the plane

LetK be a family of compact convex sets in the plane. We show that if every three members ofK admit a common line transversal, then there exist four lines which together meet all the members ofK.     

Embeddable transversal designs

The embeddability of certain (group) divisible designs in symmetric 2-designs is investigated. These designs are symmetric resolvable transversal designs. It is proved that all such transversal designs with v = 2k are embeddable and some necessary and sufficient conditions for other cases are given.     

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.     

Some properties of edge intersection graphs of single bend paths on a grid

We consider the family of intersection graphs G of paths on a grid, where every vertex v in G corresponds to a single bend path P_v on a grid, and two vertices are adjacent in G if and only if the corresponding paths share an edge on the grid. We first show that these graphs have the Erdös-Hajnal property. Then we present some properties concerning the neighborhood of a vertex in these graphs, and finally we consider some subclasses of chordal graphs for which we give necessary and sufficient conditions to be edge intersection graphs of single bend paths in a grid.