Polynomial recognition of equal unions in hypergraphs with few vertices of large degree

A family of nonempty sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions. If every point belongs to the unions, then we say the family has the full equal union property. Recognition of both properties is NP-complete even when restricted to families for which the degree of every point is at most three. In this paper we show that both recognition problems can be solved in polynomial time for families in which there is a bound on the number of points whose degree exceeds two.     

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.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

A characterization of well-covered graphs that contain neither 4- nor 5-cycles

A graph is well covered if every maximal independent set has the same cardinality. A vertex x, in a well-covered graph G, is called extendable if G – {x} is well covered and β(G) = β(G – {x}). If G is a connected, well-covered graph containing no 4- nor 5-cycles as subgraphs and G contains an extendable vertex, then G is the disjoint union of edges and triangles together with a restricted set of edges joining extendable vertices. There are only 3 other connected, well-covered graphs of this type that do not contain an extendable vertex. Moreover, all these graphs can be recognized in polynomial time.     

Proper and piecewise proper families of reals

I introduced the notions of proper and piecewise proper families of reals to make progress on a long standing open question in the field of models of Peano Arithmetic [5]. A family of reals is proper if it is arithmetically closed and its quotient Boolean algebra modulo the ideal of finite sets is a proper poset. A family of reals is piecewise proper if it is the union of a chain of proper families each of whom has size ≤ ω₁. Here, I investigate the question of the existence of proper and piecewise proper families of reals of different cardinalities. I show that it is consistent relative to ZFC to have continuum many proper families of cardinality ω₁ and continuum many piecewise proper families of cardinality ω₂ (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A decomposition theorem for χ1-convex sets

A set S in $\text{R}$ is said to be χ-convex if and only if S does not contain a visually independent subset having cardinality χ. It is natural to ask when an χ-convex set may be expressed as a countable union of convex sets. Here it is proved that if S is a closed χ-convex set in the plane and $\text{R}$ has at most finitely many bounded components, then S is a countable union of convex sets. A parallel result holds in $\text{R}$ when S is a closed χ-convex set which contains all triangular regions whose relative boundaries are in S. However, the result fails for arbitrary χ-convex sets, even in the plane.     

On quasi-amorphous sets

A set is said to be amorphous if it is infinite, but cannot be written as the disjoint union of two infinite sets. The possible structures which an amorphous set can carry were discussed in [5]. Here we study an analogous notion at the next level up, that is to say replacing finite/infinite by countable/uncountable, saying that a set is quasi-amorphous if it is uncountable, but is not the disjoint union of two uncountable sets, and every infinite subset has a countably infinite subset. We use the Fraenkel–Mostowski method to give many examples showing the diverse structures which can arise as quasi-amorphous sets, for instance carrying a projective geometry, or a linear ordering, or both; reconstruction results in the style of [1] are harder to come by in this case. Received: 8 April 1999 / Published online: 3 October 2001     

Residual properties and almost equicontinuity

A propertyP of a compact dynamical system (X,f) is called a residual property if it is inherited by factors, almost one-to-one lifts and surjective inverse limits. Many transitivity properties are residual. Weak disjointness from all propertyP systems is a residual property providedP is a residual property stronger than transitivity. Here two systems are weakly disjoint when their product is transitive. Our main result says that for an almost equicontinuous system (X, f) with associated monothetic group Λ, (X, f) is weakly disjoint from allP systems iff the onlyP systems upon which Λ acts are trivial. We use this to prove that every monothetic group has an action which is weak mixing and topologically ergodic.     

On resolvable primal spaces

A topological space is called resolvable if it is a union of two disjoint dense subsets, and is n-resolvable if it is a union of n mutually disjoint dense subsets. Clearly a resolvable space has no isolated points. If f is a selfmap on X, the sets A?X with f (A)?A are the closed sets of an Alexandroff topology called the primal topology 𝒫(f ) associated with f. We investigate resolvability for primal spaces (X, 𝒫(f)). Our main result is that an Alexandroff space is resolvable if and only if it has no isolated points. Moreover, n-resolvability and other related concepts are investigated for primal spaces.     

THE NUMBER AND SIZE OF ORBITS OF SOME PERMUTATION GROUPS

Abstract

It is shown that Aut ?, the group of homeomorphisms of the rational numbers with the usual topology, has 2 ^N_o orbits on the power set P(?). We call S ? ? a moiety if S and its complement in ? are infinite. It is shown that the orbit of any moiety S under Aut ? has cardinality 2^N_o while the orbit of S under Aut(?, ≤), the group of order preserving automorphisms of ?, has cardinality N_o if and only if S is a finite union of disjoint rational intervals with rational endpoints.     

Chebyshev polynomials for disjoint compact sets

We are concerned with the problem of finding among all polynomials of degreen with leading coefficient 1, the one which has minimal uniform norm on the union of two disjoint compact sets in the complex plane. Our main object here is to present a class of disjoint sets where the best approximation can be determined explicitly for alln. A closely related approximation problem is obtained by considering all polynomials that have degree no larger thann and satisfy an interpolatory constraint. Such problems arise in certain iterative matrix computations. Again, we discuss a class of disjoint compact sets where the optimal polynomial is explicitly known for alln.Communicated by Doron S. Lubinsky     

On the cofinalities of Boolean algebras and the ideal of null sets

We will show that if the cofinality of the ideal of Lebesgue measure zero sets is equal to then there exists a Boolean algebra B of cardinality which is not a union of strictly increasing -sequence of its subalgebras. This generalizes a result of Just and Koszmider who showed that it is consistent with that such an algebra exists. Received November 21; accepted in final form April 12, 2001.     

A Note on the Sticky Matroid Conjecture

A matroid is sticky if any two of its extensions by disjoint sets can be glued together along the common restriction (that is, they have an amalgam). The sticky matroid conjecture asserts that a matroid is sticky if and only if it is modular. Poljak and Turzík proved that no rank-3 matroid having two disjoint lines is sticky. We show that, for r ≥ 3, no rank−r matroid having two disjoint hyperplanes is sticky. These and earlier results show that the sticky matroid conjecture for finite matroids would follow from a positive resolution of the rank-4 case of a conjecture of Kantor.     

Bimatroids and invariants

A bimatroid B between the sets S and T incorporates the combinatorial exchange properties of relative invariants of the special linear group acting on a vector space and its dual, or equivalently, when S and T are finite, the exchange properties fo nonsingular minors of a matrix whose columns and rows are indexed by S and T. A rather simple idea, basically that of adjoining an identity matrix, yields a construction which produces, from the bimatroid B, a matroid R on the disjoint union S T which encodes all the structure of B. This gives a method of translating matroidal concepts and results into the language of bimatroids. We also define an analog of matrix multiplication for bimatroids: This operation generalizes matroid induction and affords another combinatorial interpretation of a linear transformation.     

On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

Minimizing submodular functions over families of sets

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting cases, there exist two elementsa andb of the groundset such that the problem is equivalent to the problem of minimizing the submodular function over the sets containinga but notb. This leads to a polynomial-time algorithm for minimizing a submodular function over these families of sets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets separating two given vertices, or to the complement of a lattice family of subsets. We also derive that the second smallest value of a submodular function over a lattice family can be computed in polynomial-time. These results generalize and unify several known results.Research partially supported by NSF contract 9302476-CCR, Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.     

Criteria for the stability of the finiteness property and for the uniqueness of Barabanov norms

A set of matrices is said to have the finiteness property if the maximal rate of exponential growth of long products of matrices drawn from that set is realised by a periodic product. The extent to which the finiteness property is prevalent among finite sets of matrices is the subject of ongoing research. In this article, we give a condition on a finite irreducible set of matrices which guarantees that the finiteness property holds not only for that set, but also for all sufficiently nearby sets of equal cardinality. We also prove a theorem giving conditions under which the Barabanov norm associated to a finite irreducible set of matrices is unique up to multiplication by a scalar, and show that in certain cases these conditions are also persistent under small perturbations.     

When is the Comaximal Graph Split?

Let R be a commutative ring with non zero unity. Let Ω(R) be a graph with vertices as elements of R whose two distinct vertices x and y are adjacent if and only if Rx + Ry = R. A graph (V, E) is said to be a split graph if V is the disjoint union of two sets K and S where K induces a complete subgraph and S is an independent set. We investigate the properties of R when Ω(R) is split.     

The footballers of Croam

The vertices of the graph O_k are indexed by the (k?1)-subsets of a (2k?1)-set. Two vertices are adjacent if and only if their labelling sets are disjoint. This paper establishes that O₅ is an edge disjoint union of two Hamiltonian circuits and a 1-factor and that O₆ is an edge disjoint union of three Hamiltonian ciruits. It follows that the graphs are 5,6-edge chromatic, respectively. The latter result settles a problem of Biggs about the footballers of Croam.     

Convexity and a certain propertyP m

The propertyP _m (directly analogous to Valentine’s propertyP ₃) is used to prove several curious results concerning subsets of a topological linear space, among them the following: (a) If a closed setS has propertyP _m and containsk points of local nonconvexity no distinct pair of which can see each other viaS, thenS is the union ofm − k − 1 or fewer starshaped sets. (b) Any closed connected set with propertyP _m is polygonally connected. (c) A closed connected setS with propertyP _m is anL _m−1 set (each pair of points may be joined by a polygonal arc ofm − 1 of fewer sides inS). (d) A finite-dimensional set with propertyP _m is anL _{2m − 3} set. A new proof of Tietze’s theorem on locally convex sets is given, and various examples refute certain plausible conjectures.