Complexity of Recognizing Equal Unions in Families of Sets

A family of sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions and has the full equal union property if, in addition, all sets are included. Both recognition problems are NP-complete even when restricted to families for which the cardinality of every set is at most three. Both problems can be solved in polynomial time when restricted to families having a bounded number of sets with cardinality greater than two. A corollary is that deciding if a graph has two disjoint edge covers is in P.     

A note on equal unions in families of sets

A family of sets has the equal union property if and only if there exist two nonempty disjoint subfamilies having the same union. We prove that any n nonempty subsets of an n-element set have the equal union property if the sum of their cardinalities exceeds n(n+1)/2. This bound is tight. Among families in which the sum of the cardinalities equals n(n+1)/2, we characterize those having the equal union property.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Unions and the axiom of choice

We study statements about countable and well‐ordered unions and their relation to each other and to countable and well‐ordered forms of the axiom of choice. Using WO as an abbreviation for “well‐orderable”, here are two typical results: The assertion that every WO family of countable sets has a WO union does not imply that every countable family of WO sets has a WO union; the axiom of choice for WO families of WO sets does not imply that the countable union of countable sets is WO. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Centers and shore points of a dendroid

A bottleneck in a dendroid is a continuum that intersects every arc connecting two nonempty open sets. Every dendroid contains a point called a center which is contained in arbitrarily small bottlenecks. A subset A of a dendroid is a shore set if for every ε>0 there is a continuum in D?A with Hausdorff distance from D less than ε. If a shore set has only one point it is called a shore point. This paper explores the relationship between center points and shore points in a dendroid. We show that if a dendroid contains a strong center, then any finite union of the arc components of the set of shore points is a shore set.     

The D-property in unions of scattered spaces

We show in a direct way that a space is D if it is a finite union of subparacompact scattered spaces. This result cannot be extended to countable unions, since it is known that there is a regular space which is a countable union of paracompact scattered spaces and which is not D. Nevertheless, we show that every space which is the union of countably many regular Lindelöf C-scattered spaces has the D-property. Also, we prove that a space is D if it is a locally finite union of regular Lindelöf C-scattered spaces.     

Characterizing compact unions of two starshaped sets inR d

SetS inR ^d has propertyK ₂ if and only ifS is a finite union ofd-polytopes and for every finite setF in bdryS there exist points c₁,c₂ (depending onF) such that each point ofF is clearly visible viaS from at least one c_i,i = 1,2. The following characterization theorem is established: Let , d2. SetS is a compact union of two starshaped sets if and only if there is a sequence {S _j } converging toS (relative to the Hausdorff metric) such that each setS _j satisfies propertyK ₂. For , the sufficiency of the condition above still holds, although the necessity fails.     

Convex -closures versus convex norm-closures in dual Banach spaces

A subset Y of a dual Banach space X^* is said to have the property (P) if for every weak^*-compact subset H of Y. The purpose of this paper is to give a characterization of the property (P) for subsets of a dual Banach space X^*, and to study the behavior of the property (P) with respect to additions, unions, products, whether the closed linear hull has the property (P) when Y does, etc. We show that the property (P) is stable under all these operations in the class of weak^* -analytic subsets of X^*.     

General Existence Theorem of Zero Points

Let X be a nonempty, compact, convex set in and let be an upper semicontinuous mapping from X to the collection of nonempty, compact, convex subsets of . It is well known that such a mapping has a stationary point on X; i.e., there exists a point X such that its image under has a nonempty intersection with the normal cone of X at the point. In the case where, for every point in X, it holds that the intersection of the image under with the normal cone of X at the point is either empty or contains the origin 0 ⁿ , then must have a zero point on X; i.e., there exists a point in X such that 0 ⁿ lies in the image of the point. Another well-known condition for the existence of a zero point follows from the Ky Fan coincidence theorem, which says that, if for every point the intersection of the image with the tangent cone of X at the point is nonempty, the mapping must have a zero point. In this paper, we extend all these existence results by giving a general zero-point existence theorem, of which the previous two results are obtained as special cases. We discuss also what kind of solutions may exist when no further conditions are stated on the mapping . Finally, we show how our results can be used to establish several new intersection results on a compact, convex set.     

Strongly balanced cooperative games

Kaneko/Wooders (1982) derived a list of necessary and sufficient conditions for a partitioning game to have a nonempty core regardless of the payoff functions of its effective coalitions. The main purpose of our paper is to provide a graph-theoretical characterization of this family of games whose associated hypergraphs we callstrongly balanced: we show that the strong balancedness condition is equivalent to thenormality of the hypergraph, which is a type ofcoloring property (Lovasz (1972)). We also study interesting economic examples ofcommunication andassignment games and provide direct proofs that their associated hypergraphs are strongly balanced.We wish to thank two anonymous referees of this journal for their useful comments and suggestions. The previous version of this paper was written while the authors were visiting Department of Economics, University of Bonn. The financial support of Sonderfor-schungsbereich 303 is gratefully acknowledged.     

A Helly-Type Theorem for Intersections of Compact Connected Sets in the Plane

For a family C of nonempty compact sets in the plane, the following conditions are equivalent:(1) Every two (not necessarily distinct) members of C have a connected union and every three (not necessarily distinct) members of C have a simply connected union.(2) C is a family of simply connected sets such that every two (not necessarily distinct) members of C have a connected intersection and every three (not necessarily distinct) members of C have a nonempty intersection.If either set of conditions is satisfied, then { C : C in C } is nonempty, simply connected, and connected. Furthermore, if the collection C is finite, then it is also true that { C : C in C } is simply connected.     

Theorem on directed graphs,applicable to logic

A semicycle is said to turn at a point a if the arcs incident to a are both to it or both from it. We prove that if a nonempty set of points of a finite directed graph contains a turning point of each semicycle, then one of its members is a turning point of every semicycle to which it belongs; and we indicate the application of this result to mathematical logic through the modeling of arguments by graphs.     

Connector Families of Graphs

For every pair of fixed natural numbers k > l we consider families of subgraphs of the complete graph K _n such that each graph in the family has at least k connected components while the union of any two has at most l. We show that the cardinality of such a family is at most exponential in n and determine the exact exponential growth of the largest such families for every value of k and l = 1.     

Isols and maximal intersecting classes

In transfinite arithmetic 2ⁿ is defined as the cardinality of the family of all subsets of some set v with cardinality n. However, in the arithmetic of recursive equivalence types (RETs) 2^N is defined as the RET of the family of all finite subsets of some set v of nonnegative integers with RET N. Suppose v is a nonempty set. S is a class over v, if S consists of finite subsets of v and has v as its union. Such a class is an intersecting class (IC) over v, if every two members of S have a nonempty intersection. An IC over v is called a maximal IC (MIC), if it is not properly included in any IC over v. It is known and readily proved that every MIC over a finite set v of cardinality n ≥ 1 has cardinality 2^n-1. In order to generalize this result we introduce the notion of an ω-MIC over v. This is an effective analogue ot the notion of an MIC over v such that a class over a finite set v is an ω-MIC iff it is an MIC. We then prove that every ω-MIC over an isolated set v of RET N ≥ 1 has RET 2^N-1. This is a generalization, for while there only are χ₀ finite sets, there are ? isolated sets, where c denotes the cardinality of the continuum, namely all the finite sets and the c immune sets. MSC: 03D50.     

Common fixed point theorems and minimax inequalities in locally convex Hausdorff topological vector spaces

In this article, we introduce the concept of a family of set-valued mappings generalized Knaster–Kuratowski–Mazurkiewicz (KKM) w.r.t. other family of set-valued mappings. We then prove that if X is a nonempty compact convex subset of a locally convex Hausdorff topological vector space and 𝒯 and 𝒮 are two families of self set-valued mappings of X such that 𝒮 is generalized KKM w.r.t. 𝒯, under some natural conditions, the set-valued mappings S ∈ 𝒮 have a fixed point. Other common fixed point theorems and minimax inequalities of Ky Fan type are obtained as applications.     

An intersection property for starshaped sets in the plane

Let be a family of compact starshaped sets in the plane. If every three and every two members of have a union which is connected and simply connected, then {F:F in } is simply connected and nonempty. Of course, if every three and every two members of have a starshaped union, the same result holds.Supported in part by NSF grants DMS-8705336, DMS-8908717 and by a Senior Faculty Summer Research Fellowship, Research Council, University of Oklahoma.     

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     

A Krasnosel’skii-type result for planar sets starshaped via orthogonally convex paths

A Krasnosel’skii-type theorem for compact sets that are starshaped via staircase paths may be extended to compact sets that are starshaped via orthogonally convex paths: Let S be a nonempty compact planar set having connected complement. If every two points of S are visible via orthogonally convex paths from a common point of S, then S is starshaped via orthogonally convex paths. Moreover, the associated kernel Ker S has the expected property that every two of its points are joined in Ker S by an orthogonally convex path. If S is an arbitrary nonempty planar set that is starshaped via orthogonally convex paths, then for each component C of Ker S, every two of points of C are joined in C by an orthogonally convex path. Communicated by Imre Bárány     

Strong Version of the Basic Deciding Algorithm for the Existential Theory of Real Fields

Let U be a real algebraic variety in the n-dimensional affine space that is a set of all zeros of a family of polynomials of degree less than d. In the case where U is bounded (this is the main case), an algorithm of polynomial complexity is described for constructing a subset of U with the number of elements bounded from above by dⁿ that has the following property: for every s, this set has a nonempty intersection with every d-dimensional cycle with coefficients from s of the closure of the set of smooth points of dimension s of U. Bibliography: 16 titles.     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.