A minimax theorem for chain complete ordered sets

It is shown that if a chain complete ordered set does not have k+1 pairwise disjoint maximal chains for some finite k, then the minimum size of a cutset is equal to the maximum size of a collection of pairwise disjoint maximal chains. This answers a question of Pouzet and Zaguia.The author was supported in part by ONR grant N00014-85K-0494 and NSERC grants 69-3378, 69-0259, and 69-1325.     

Maximal chains and cutsets of an ordered set: A menger type approach

We prove the following results which are related to Menger's theorem for (infinite) ordered sets. (i) If the space of maximal chains of an ordered set is compact, then the maximum number of pairwise disjoint maximal chains is finite and is equal to the minimum size of a cutset, (i.e. a set which meets all maximal chains). (ii) If the maximal chains pairwise intersect, then the intersection of finitely many is never empty. One corollary of (ii) is that, if the maximal chains pairwise intersect and if one of the maximal chains is complete, then there is an element common to all maximal chains.     

Compactness and subsets of ordered sets that meet all maximal chains

LetP be a chain complete ordered set. By considering subsets which meet all maximal chains, we describe conditions which imply that the space of maximal chains ofP is compact. The symbolsP ₁ andP ₂ refer to two particular ordered sets considered below. It is shown that the space of maximal chains (P) is compact ifP satisfies any of the following conditions: (i)P contains no copy ofP ₁ or its dual and all antichains inP are finite. (ii)P contains no properN and every element ofP belongs to a finite maximal antichain ofP. (iii)P contains no copy ofP ₁ orP ₂ and for everyx inP there is a finite subset ofP which is coinitial abovex. We also describe an example of an ordered set which is complete and densely ordered and in which no antichain meets every maximal chain.     

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

and let be the collection of all subsets of [n] ordered by inclusion. is a cutset if it meets every maximal chain in , and the width of is the minimum number of chains in a chain decomposition of . Fix . What is the smallest value of such that there exists a cutset that consists only of subsets of sizes between m and l, and such that it contains exactly k subsets of size i for each ? The answer, which we denote by , gives a lower estimate for the width of a cutset between levels m and l in . After using the Kruskal–Katona Theorem to give a general characterization of cutsets in terms of the number and sizes of their elements, we find lower and upper bounds (as well as some exact values) for . Received September 4, 1997     

On the size of maximal antichains and the number of pairwise disjoint maximal chains

Fix integers n and k with n≥k≥3. Duffus and Sands proved that if P is a finite poset and n≤|C|≤n+(n−k)/(k−2) for every maximal chain in P, then P must contain k pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if P is a finite poset and n≤|A|≤n+(n−k)/(k−2) for every maximal antichain in P, then P has k pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.     

On the size of maximal chains and the number of pairwise disjoint maximal antichains

For each integer k≥3, we find all maximal intervals I_k of natural numbers with the following property: whenever the number of elements in every maximal chain in a finite partially ordered set P lies in I_k, then P contains k pairwise disjoint maximal antichains. All such I_k are of the form

     

Infinite ordered sets spanned by finitely many chains

We say that an ordered set P is spanned by a family C of chains if P=(P, ) is the transitive closure of {(C, | C) C C. It is shown that there is a function h: such that if P is spanned by k< chains, then P has a finite cutset-number h(k) (i.e. for any xP, there is a finite set F of size |F|h(k)–1, such that the elements of F are incomparable with x and {x}F meets every maximal chain of P). The function h is exponentially bounded but eventually dominates any polynomial function, even if it is only required that there are at most h(k) pairwise disjoint maximal chains in P, whenever P is spanned by k< chains.     

When Will Every Maximal <Emphasis Type="BoldItalic">F</Emphasis>-free Subposet Contain a Maximal Element?

Let F be a partially ordered set (poset). A poset P is called F-free if P contains no subposet isomorphic to F. A finite poset F is said to have the maximal element property if every maximal F-free subposet of any finite poset P contains a maximal element of P. It is shown that a poset F with at least two elements has the maximal element property if and only if F is an antichain or F ≅ 2 + 2.     

On lightly and countably compact spaces in ZF

Abstract

Given a topological space X = (X, T ), we show in the Zermelo-Fraenkel set theory ZF that:

1. Every locally finite family of open sets of X is finite iff every pairwise disjoint, locally finite family of open sets is finite.

2. Every locally finite family of subsets of X is finite iff every pairwise disjoint, locally finite family of subsets of X is finite iff every locally finite family of closed subsets of X is finite.

3. The statement “every locally finite family of closed sets of X is finite” implies the proposition “every locally finite family of open sets of X is finite”. The converse holds true in case X is T₄ and the countable axiom of choice holds true.

   We also show:

4. It is relatively consistent with ZF the existence of a non countably compact T₁ space such that every pairwise disjoint locally finite family of closed subsets is finite but some locally finite family of subsets is infinite.

5. It is relatively consistent with ZF the existence of a countably compact T₄ space including an infinite pairwise disjoint locally finite family of open (resp. closed) sets.

     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

A proof of dilworth’s decomposition theorem for partially ordered sets

A short proof of the following theorem is given: LetP be a finite partially ordered set. If the maximal number of elements in an independent subset ofP isk, thenP is the union ofk chains.     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

More on Poincaré’s and Perron’s Theorems for Difference Equations∗

Consider the scalar kth order linear difference equation: x(n + k) + pi(n)x(n + k - 1) + … + pk(n)x(n) = 0 where the limits qi=lim_n→∞Pi(n) (i=1,…,k) are finite. In this paper, we confirm the conjecture formulated recently by Elaydi. Namely, every nonzero solution x of (?) satisfies the same asymptotic relation as the fundamental solutions described earlier by Perron, ie., ?= lim sup_n→∞ |x(n)| is equal to the modulus of one of the roots of the characteristics equation χ ^k + q ₁χ ^k?1+…+qk=0. This result is a consequence of a more general theorem concerning the Poincaré difference system x(n+1)=[A+B(n]x(n), where A and B(n) (n=0,1,…) are square matrices such that ‖B(n)‖ →0 as n → ∞. As another corollary, we obtain a new limit relation for the solutions of (?).     

Regressions and monotone chains: A ramsey-type extremal problem for partial orders

Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx ₁<x ₂ <...<x _k such thatg(x ₁)≦g(x ₂)≦...≦g(x _k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) ^k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451.     

Exixtence of vertices of local connectivityk in digraphs of large outdegree

For every positive integerk, there is a positive integerf(k) such that every finite digraph of minimum outdegreef(k) contains verticesx, y joined byk openly disjoint paths.     

Vertex disjoint equivalent subgraphs of order 3

Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007     

Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

Edge disjoint cycles through specified vertices

We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2k‐connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V(G)|/2 + 2(k ? 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V(G)). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2k connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G[Y]. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Openly disjoint circuits through a vertex in regular digraphs

In 1985, Thomassen [14] constructed for every positive integer r, finite digraphs D of minimum degree δ(D)=r which do not contain a vertex x lying on three openly disjoint circuits, i.e. circuits which have pairwise exactly x in common. In 2005, Seymour [11] posed the question, whether an r-regular digraph contains a vertex x such that there are r openly disjoint circuits through x. This is true for r≤3, but does not hold for r≥8. But perhaps, in contrast to the minimum degree, a high regularity degree suffices for the existence of a vertex lying on r openly disjoint circuits also for r≥4. After a survey of these problems, we will show that every r-regular digraph with r≥7 has a vertex which lies on 4 openly disjoint circuits.     

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