Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

Connectedness and diameter for random orders of fixed dimension

Let P _k (n) be the (partial) order determined by intersecting k random linear orderings of a set of size n; equivalently, let P _k (n) consist of n points chosen randomly and independently from the unit cube in ^k , with the induced product order. We show for each fixed k>1, that with probability approaching 1 as n, the comparability graph of P _k (n) is connected and has diameter 3.     

A combinatorial bijection between linear extensions of equivalent orders

Let P and Q be (partially) ordered sets with the same comparability graph. A bijection is constructed between the sets of linear extensions of P and Q such that the number of setups is preserved. This yields a common generalization of the comparability invariance of order dimension, setup number and number of linear extensions.     

A class of matroids derived from saturated chain partitions of partially ordered sets

The simultaneously k- and (k − 1)-saturated chain partitions of a finite partially ordered set P determine a matroid G_k(P). This matroid is a gammoid. The identity on P induces a strong map from G_k(P) to G_{k + 1}(P). This strong map has a linear representation.     

Note: Semi-Order Dimension Two is a Comparability Invariant

A partial order P =(X, < _P ) is a semi-order if it is an interval order admitting an interval representation such that all the intervals are of unit length. The semi-order dimension of P is the smallest k for which there exist k semi-order extensions of P which realize P. In 1992 the question whether semi-order dimension is a comparability invariant was posed. We prove that for k = 2 this is the case.     

Uncountable Homogeneous Partial Orders

A partially ordered set (P, ≤) is called k‐homogeneous if any isomorphism between k‐element subsets extends to an automorphism of (P, ≤). Assuming the set‐theoretic assumption ⋄(ϰ₁), it is shown that for each k, there exist partially ordered sets of size ϰ₁ which embed each countable partial order and are k‐homogeneous, but not (k + 1)‐homogeneous. This is impossible in the countable case for k ≥ 4.     

Being a Proper Trapezoid Ordered Set Is a Comparability Invariant

It is proved that if we replace an autonomous subset of a finite proper trapezoid ordered set with a proper trapezoid ordered set, then we obtain a proper trapezoid ordered set provided the autonomous subset is not an antichain, and analogously in the k-dimensional case. As corollaries we obtain that being a proper trapezoid ordered set is a comparability invariant, more generally, proper interval dimension is a comparability invariant.     

A relation between the comparability graph and the number of linear extensions

In this note, we prove that the comparability graph of a posetP has less edges than that of a posetQ on the same set of elements, thenP has more linear extensions thanQ. This solves a problem posed by Kelly [1].Research partially supported by the grant RP.I.09 from the Institute of Informatics, University of Warsaw.     

VC-Dimension of Sets of Permutations

VC-dimension of a set of permutations to be the maximal k such that there exist distinct that appear in A in all possible linear orders, that is, every linear order of is equivalent to the standard order of for at least one permutation . In other words, the VC-dimension of A is the maximal k such that for some the restriction of A to contains all possible linear orders. This is analogous to the VC-dimension of a set of strings. Our main result is that there exists a universal constant C such that any set of permutations with VC-dimension 2 is of size . This is analogous to Sauer's lemma for the case of VC-dimension 2. One corollary of our main result is that any acyclic set of linear orders of is of size , (a set A of linear orders on is called acyclic if no 3 elements appear in A in all 3 orders (i,j,k), (k,i,j) and (j,k,i)). The size of the largest acyclic set of linear orders has interested researchers for many years because it is the largest number of linear orders of n alternatives such that the following is always satisfied: if each one of a set of voters chooses one of these orders as his preference then the majority relation between each two alternatives is transitive. Received August 6, 1998     

On the<Emphasis Type="Italic">k</Emphasis>-systems of a simple polytope

Ak-system of the graphG _P of a simple polytopeP is a set of induced subgraphs ofG _P that shares certain properties with the set of subgraphs induced by thek-faces ofP. This new concept leads to polynomial-size certificates in terms ofG _P for both the set of vertex sets of facets and for abstract objective functions (AOF) in the sense of Kalai. Moreover, it is proved that an acyclic orientation yields an AOF if and only if it induces a unique sink on every 2-face.     

A characterization of graphs without long induced paths

In a connected graph define the k-center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d-dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d. Call a graph P_t-free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P_2k-1-free (P_2k-free) if and only if each of its connected induced subgraphs H satisfy the following property: The k-center of H (k - 1)-dominates ((k - 2)-dominates) H. Moreover, we show that the subgraph induced by the (t - 3)-center in any P_t-free connected graph is again connected and has diameter at most t - 3.     

Path-Bicolorable Graphs

In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k ≥ 2, a graph G = (V, E) is P _k -bicolorable if its vertex set V can be partitioned into two subsets (i.e., color classes) V ₁ and V ₂ such that for every induced P _k (a path with exactly k − 1 edges and k vertices) in G, the two colors alternate along the P _k , i.e., no two consecutive vertices of the P _k belong to the same color class V _i , i = 1, 2. Obviously, a graph is bipartite if and only if it is P ₂-bicolorable. We give a structural characterization of P ₃-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of P ₄-bicolorable graphs in terms of forbidden subgraphs.     

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.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

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.     

Analytic Hypoellipticity at Non-Symplectic Poisson-Treves Strata for Certain Sums of Squares of Vector Fields

We consider an operator P which is a sum of squares of vector fields with analytic coefficients. The operator has a non-symplectic characteristic manifold, but the rank of the symplectic form σ is not constant on Char P. Moreover the Hamilton foliation of the non-symplectic stratum of the Poisson-Treves stratification for P consists of closed curves in a ring-shaped open set around the origin. We prove that then P is analytic hypoelliptic on that open set. And we note explicitly that the local Gevrey hypoellipticity for P is G ^k+1 and that this is sharp.      

On Linear Groups of Degree 2n Containing a Representation of the Special Linear Group of Degree n

Let n be an integer, n ≥ 2, and let a field P be a quadratic extension of an infinite field k. Regarding P as a k-vector space of dimension 2, we consider an n-dimensional P-vector space V as a 2n-dimensional k-vector space so the general linear group GL _n (P) acting on V is embedded in the group GL _2n (k). Let a field K be an algebraic extension of k. In this article, we determine overgroups of the special linear group SL _n (P) in the group GL _2n (K).     

On Minimum-Weight k-Edge Connected Steiner Networks on Metric Spaces

For a given set of points P in a metric space, let w _k(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r _k=inf{w _k(P) |P}. We show in this paper that for any P, , for even k≥2 and , for odd k≥3. In particular, we prove that for any P in the Euclidean plane, w ₄(P) and w ₅(P) are greater than or equal to , and ; For any P in the rectilinear plane , for odd k≥5. In addition, we prove that there exists an O(|P|³)-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of for even k and for odd k. Received: August 21, 1997 Revised: February 5, 1998     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.