On Geometric Graph Ramsey Numbers

For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings in multicoloured geometric graphs. Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867.     

Covering Paths for Planar Point Sets

Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n?1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+O(n/logn) straight line segments. If the path is required to be noncrossing, we prove that (1?ε)n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5n/9?O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω(nlogn) time in the worst case.     

The Minimal Length of a Closed Geodesic Net on a Riemannian Manifold with a Nontrivial Second Homology Group

Let Mⁿ be a closed Riemannian manifold with a nontrivial second homology group. In this paper we prove that there exists a geodesic net on Mⁿ of length at most 3 diameter(Mⁿ). Moreover, this geodesic net is either a closed geodesic, consists of two geodesic loops emanating from the same point, or consists of three geodesic segments between the same endpoints. Geodesic nets can be viewed as the critical points of the length functional on the space of graphs immersed into a Riemannian manifold. One can also consider other natural functionals on the same space, in particular, the maximal length of an edge. We prove that either there exists a closed geodesic of length ≤ 2 diameter(Mⁿ), or there exists a critical point of this functional on the space of immersed θ-graphs such that the value of the functional does not exceed the diameter of Mⁿ. If n=2, then this critical θ-graph is not only immersed but embedded.Mathematics Subject Classifications (2000). 53C23, 49Q10     

Ramsey-Type Results for Geometric Graphs, I

For any 2-coloring of the segments determined by n points in general position in the plane, at least one of the color classes contains a non-self-intersecting spanning tree. Under the same assumptions, we also prove that there exist pairwise disjoint segments of the same color, and this bound is tight. The above theorems were conjectured by Bialostocki and Dierker. Furthermore, improving an earlier result of Larman et al., we construct a family of m segments in the plane, which has no more than members that are either pairwise disjoint or pairwise crossing. Finally, we discuss some related problems and generalizations. Received October 17, 1995, and in revised form February 10, 1996.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Linked partitions and linked cycles

The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schröder number r_n, which counts the number of Schröder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

A ramsey-type bound for rectangles

It is proved that for any rectangle T and for any 2-coloring of the points of the 5-dimensional Euclidean space, one can always find a rectangle T′ congruent to T, all of whose vertices are of the same color. We also show that for any k-coloring of the k² + o(k²)-dimensional space, there is a monochromatic rectangle congruent to any given rectangle. © 1996 John Wiley & Sons, Inc.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

Noncrossing trees are almost conditioned Galton–Watson trees

A noncrossing tree (NC‐tree) is a tree drawn on the plane having as vertices a set of points on the boundary of a circle, and whose edges are straight line segments that do not cross. In this article, we show that NC‐trees with size n are conditioned Galton–Watson trees. As corollaries, we give the limit law of depth‐first traversal processes and the limit profile of NC‐trees. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 115–125, 2002     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

Long Monochromatic Berge Cycles in Colored 4-Uniform Hypergraphs

Here we prove that for n ≥ 140, in every 3-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a monochromatic Berge cycle of length at least n − 10. This result sharpens an asymptotic result obtained earlier. Another result is that for n ≥ 15, in every 2-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a 3-tight Berge cycle of length at least n − 10.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

Cycles of given color patterns

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph K^c_n on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in K^c_n with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K^c_n contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Sub-Ramsey Numbers for Arithmetic Progressions

Let the integers 1, . . . ,n be assigned colors. Szemerédi's theorem implies that if there is a dense color class then there is an arithmetic progression of length three in that color. We study the conditions on the color classes forcing totally multicolored arithmetic progressions of length 3. Let f(n) be the smallest integer k such that there is a coloring of {1, . . . ,n} without totally multicolored arithmetic progressions of length three and such that each color appears on at most k integers. We provide an exact value for f(n) when n is sufficiently large, and all extremal colorings. In particular, we show that f(n)=8n/17+O(1). This completely answers a question of Alon, Caro and Tuza.     

The Number of Geometric Bistellar Neighbors of a Triangulation

The theory of secondary and fiber polytopes implies that regular (also called convex or coherent) triangulations of configurations with n points in R ^d have at least n-d-1 geometric bistellar neighbors. Here we prove that, in fact, all triangulations of n points in R ² have at least n-3 geometric bistellar neighbors. In a similar way, we show that for three-dimensional point configurations, in convex position and with no three points collinear, all triangulations have at least n-4 geometric bistellar flips. In contrast, we exhibit three-dimensional point configurations, with a single interior point, having deficiency on the number of geometric bistellar flips. A lifting technique allows us to obtain a triangulation of a simplicial convex 4-polytope with less than n-5 neighbors. We also construct a family of point configurations in R ³ with arbitrarily large flip deficiency. Received November 25, 1996, and in revised form March 10, 1997.     

Testing Homotopy for Paths in the Plane

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For paths specified by n line segments with obstacles described by n points, several standard ways achieve quadratic running time. For simple paths, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcrofts problem; our algorithm runs in O(n ^3/2log n) time.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

Polyhedral line transversals in space

Algorithms are developed for determining if a set of polyhedral objects inR ³ can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n ⁴ logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.