On separating systems whose elements are sets of at most k elements

A system A₁,…,A_m of subsets of X?{1,…,n} is called a separating system if for any two distinct elements of X there is a set A_i (1?i?m) that contains exactly one of the two elements. We investigate separating systems where each set A_i has at most k elements and we are looking for minimal separating systems, that means separating systems with the least number of subsets. We call this least number m(n,k). Katona has proved good bounds on m(n,k) but his proof is very complicated. We give a shorter and easier proof. In doing so we slightly improve the upper bound of Katona.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

Score sets ink-partite tournaments

The set S of distinct scores (outdegrees) of the vertices of ak-partite tournamentT(X ₁, X₂, ···, X_k) is called its score set. In this paper, we prove that every set of n non-negative integers, except {0} and {0, 1}, is a score set of some 3-partite tournament. We also prove that every set ofn non-negative integers is a score set of somek-partite tournament for everyn ≥k ≥ 2.     

l-trace k-Sperner families of sets

A family of sets F⊆X² is defined to be l-trace k-Sperner if for any subset Y of X with size l the trace of F on Y (the restriction of F to Y) does not contain any chain of length k+1. In this paper we investigate the maximum size that an l-trace k-Sperner family (with underlying set [n]={1,2,…,n}) can have for various values of k, l and n.     

Generating all subsets of a finite set with disjoint unions

If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3.     

Convex Pencils of Real Quadratic Forms

We study the topology of the set X of the solutions of a system of two quadratic inequalities in the real projective space ?P ⁿ (e.g. X is the intersection of two real quadrics). We give explicit formulas for its Betti numbers and for those of its double cover in the sphere S ⁿ ; we also give similar formulas for level sets of homogeneous quadratic maps to the plane. We discuss some applications of these results, especially in classical convexity theory. We prove the sharp bound b(X)??2n for the total Betti number of X; we show that for odd n this bound is attained only by a singular?X. In the nondegenerate case we also prove the bound on each specific Betti number b _k (X)??2(k+2).     

Quartets in maximal weakly compatible split systems

Weakly compatible split systems are a generalization of unrooted evolutionary trees and are commonly used to display reticulate evolution or ambiguity in biological data. They are collections of bipartitions of a finite set X of taxa (e.g. species) with the property that, for every four taxa, at least one of the three bipartitions into two pairs (quartets) is not induced by any of the X-splits. We characterize all split systems where exactly two quartets from every quadruple are induced by some split. On the other hand, we construct maximal weakly compatible split systems where the number of induced quartets per quadruple tends to 0 with the number of taxa going to infinity.     

A note on the kernels of higher derivations

Let k ? k′ be a field extension. We give relations between the kernels of higher derivations on k[X] and k′[X], where k[X]:= k[x ₁,…, x _n ] denotes the polynomial ring in n variables over the field k. More precisely, let D = {D _n } _n=0 ^∞ a higher k-derivation on k[X] and D′ = {D′ _n } _n=0 ^∞ a higher k′-derivation on k′[X] such that D′ _m (x _i ) = D _m (x _i ) for all m ? 0 and i = 1, 2,…, n. Then (1) k[X] ^D = k if and only if k′[X] ^D′ = k′; (2) k[X] ^D is a finitely generated k-algebra if and only if k′[X] ^D′ is a finitely generated k′-algebra. Furthermore, we also show that the kernel k[X] ^D of a higher derivation D of k[X] can be generated by a set of closed polynomials.     

Parallel realization of permutations over trees

Let G = (X,E) be a finite connected (undirected) graph; a permutation σ over X is said to be compatible with G when every vertex x different from σ(x) is adjacent to σ(x); l(G) denotes the minimum k such that every permutation over X can be decomposed into a product of k permutations compatible with G. It is shown that, among all trees with X as set of vertices, the chain has the smallest l(G).     

Note on the locally product and almost locally product structures

This paper is concerned with a study of some of the properties of locally product and almost locally product structures on a differentiable manifold X _n of class C ^k . Every locally product space has certain almost locally product structures which transform the local tangent space to X _n at an arbitrary point P in a set fashion: this is studied in Theorem (2.2). Theorem (2.3) considers the nature of transformations that exist between two co-ordinate systems at a point whenever an almost locally product structure has the same local representation in each of these co-ordinate systems. A necessary and sufficient condition for X _n to be a locally product manifold is obtained in terms of the pseudo-group of co-ordinate transformations on X _n and the subpseudo-groups [cf., Theoren (2.1)]. Section 3 is entirely devoted to the study of integrable almost locally product structures.     

Splitting manifolds as M × R where M has a k-fold end structure

Let X be a locally finite simplicial complex of dimension n, n? 5, equipped with a k-fold end structure [4] and consider a piecewise linear (n + 1)-dimensional manifold M that is proper homotopy equivalent to X × R by F:M → X × R, where R is the set of real numbers. The question arises as to whether or not the manifold M can be split, i.e., written as M = N × R where N is a n-manifold and where there is a proper homotopy between F and (p₁ ° F₀) × id:N × R → X × R, preserving the natural (k+1)-fold end structure, where F₀ is F|_N and p₁ is the projection X × R → X. Of particular significance is the fact that X is noncompact. When the construction of such splittings is attempted, algebraic obstructions arise, which vanish if and only if the construction can be completed. This paper develops such an obstruction theory by utilizing methods of L.C. Siebenmann and the k-fold end structures of F. Waldhausen.     

Minimum Covering for Hexagon Triple Systems

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c,z,a), where a, b, c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b,y,c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kK ⁿ with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kK ⁿ with hexagon triples is a triple (X, H, P) such that: 1.3kK ⁿ has vertex set X. 2.P is a subset of E(λ K ⁿ ) with vertex set X for some λ, and 3.H is an edge disjoint partition of E(3kK ⁿ )∪ P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kK ⁿ with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kK ⁿ with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kK ⁿ with hexagon triples was given recently by the authors [2]. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kK ⁿ with hexagon triples.     

Nilpotency of unstable K-theory

In the preceding papers [H. Hamanaka, A. Kono, On [X,U(n)], when dimX is 2n, J. Math. Kyoto Univ. 43 (2) (2003) 333-348; H. Hamanaka, On [X,U(n)], when dimX is 2n+1, J. Math. Kyoto Univ. 44 (3) (2004) 655-667; H. Hamanaka, Adams e-invariant, Toda bracket and [X,U(n)], J. Math. Kyoto Univ. 43 (4) (2003) 815-828], the group structure of the homotopy set [X,U(n)] with the pointwise multiplication is studied, where X is a finite CW-complex and U(n) is the unitary group. It is seen that nil[X,U(n)]=2 for some X with its dimension 2n, and, when dimX=2n+1 and n is even, [X,U(n)] is expressed as the two stage central extension of an Abelian group, i.e., nil[X,U(n)]?3.In this paper, we consider the nilpotency class of [X,U(n)], especially, for given k, the maximum of the nil[X,U(n)] under the condition dimX?2n+k is estimated and determined for k=0,1,2.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

A packing problem its application to Bose's families

We propose and study the following problem: given X ⊂ Z_n, construct a maximum packing of dev X (the development of X), i.e., a maximum set of pairwise disjoint translates of X. Such a packing is optimal when its size reaches the upper bound . In particular, it is perfect when its size is exactly equal to i.e. when it is a partition of Z_n. We apply the above problem for constructing Bose's families. A (q, k) Bose's family (BF) is a nonempty family F of subsets of the field GF(q) such that: (i) each member of F is a coset of the kth roots of unity for k odd (the union of a coset of the (k - 1)th roots of unity and zero for k even); (ii) the development of F, i.e., the incidence structure , is a semilinear space. A (q, k)-BF is optimal when its size reaches the upper bound . In particular, it is perfect when its size is exactly equal to ; in this case the (q, k)-BF is a (q, k, 1) difference family and its development is a linear space. If the set of (q, k)-BF's is not empty, there is a bijection preserving maximality, optimality, and perfectness between this set with the set of packings of dev X, where X is a suitable -subset of Z_n, for k odd, for k even. © 1996 John Wiley & Sons, Inc.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Split orders and convex polytopes in buildings

As part of his work to develop an explicit trace formula for Hecke operators on congruence subgroups of SL₂(Z), Hijikata (1974) [13] defines and characterizes the notion of a split order in M₂(k), where k is a local field. In this paper, we generalize the notion of a split order to Mn(k) for n>2 and give a natural geometric characterization in terms of the affine building for SLn(k). In particular, we show that there is a one-to-one correspondence between split orders in Mn(k) and a collection of convex polytopes in apartments of the building such that the split order is the intersection of all the maximal orders representing the vertices in the polytope. This generalizes the geometric interpretation in the n=2 case in which split orders correspond to geodesics in the tree for SL₂(k) with the split order given as the intersection of the endpoints of the geodesic.     

Hereditary normality of a space of the form ℱ(<Emphasis Type="Italic">X</Emphasis>)

Assuming the continuum hypothesis we construct an example of a nonmetrizable compact set X with the following properties(1) X ⁿ is hereditarily separable for all n ∈ ?(2) X ⁿ \ Δ _n is perfectly normal for every n ∈ ?, where Δ _n is the generalized diagonal of X ⁿ , i.e., the set of points with at least two equal coordinates(3) for every seminormal functor ? that preserves weights and the points of bijectivity the space ? _k (X) is hereditarily normal, where k is the second smallest element of the power spectrum of the functor ?; in particular, X ² and λ ₃ X are hereditarily normal.Our example of a space of this type strengthens the well-known example by Gruenhage of a nonmetrizable compact set whose square is hereditarily normal and hereditarily separable.     

Sequential properties of function spaces with the compact-open topology

The main results of the paper are:

(1)

If X is metrizable but not locally compact topological space, then Ck(X) contains a closed copy of S₂, and hence does not have the property AP;

(2)

For any zero-dimensional Polish X, the space Ck(X,2) is sequential if and only if X is either locally compact or the derived set X^′ is compact; and

(3)

All spaces of the form Ck(X,2), where X is a non-locally compact Polish space whose derived set is compact, are homeomorphic, and have the topology determined by an increasing sequence of Cantor subspaces, the nth one nowhere dense in the (n+1)st.

     

Embedding finite posets in cubes

In this paper we define the n-cube Q_n as the poset obtained by taking the cartesian product of n chains each consisting of two points. For a finite poset X, we then define dim₂X as the smallest positive integer n such that X can be embedded as a subposet of Q_n. For any poset X we then have log₂ |X| ? dim₂X ? |X|. For the distributive lattice $\text{L =}\text{2}{}^{\mathrm{X}}$, dim₂L = |X| and for the crown S^k_n, dim₂ (S^k_n) = n + k. For each k ? 2, there exist positive constants c₁ and c₂ so that for the poset X consisting of all one element and k-element subsets of an n-element set, the inequality c₁ log₂n < dim₂(X) < c₂ log₂n holds for all n with k < n. A poset is called Q-critical if dim₂ (X ? x) < dim₂(X) for every x ? X. We define a join operation ⊕ on posets under which the collection Q of all Q-critical posets which are not chains forms a semigroup in which unique factorization holds. We then completely determine the subcollection $\text{M}$ ? Q consisting of all posets X for which dim₂ (X) = |X|.