On the edge-colouring problem for unions of complete uniform hypergraphs

For given n∈$\text{N}$ and H?{1,2,…,n} we investigate whether the collection of subsets A?{1,2,…,n} with |A|∈H possesses a parellelism (1-factorization). A complete solution for the case H={1,2,…, h} is given.     

Sixteen topological types in βω−ω

In this paper we describe sixteen topological types in βω?ω. Among others, we show that there is a weak P-point x ∈ βω?ω which is a limit point of some ccc subset of βω?ω?{x} and that there is a point y ∈ βω?ω which is a limit point of some countable subset of βω?ω?{y} but not of any countable discrete subset of βω?ω?{y}.     

Note: On the generalized spectral characterization of graphs having an isolated vertex

In this paper, some sufficient conditions are given on a graph G, under which it is proved that G?{x} is determined by the generalized spectrum iff G is determined by the generalized spectrum, where G?{x} is the graph obtained from the graph G by adding an isolated vertex x.     

An asymptotic formula for the maximum size of an h-family in products of partially ordered sets

An h-family of a partially ordered set P is a subset of P such that no h + 1 elements of the h-family lie on any single chain. Let S₁, S₂,… be a sequence of partially ordered sets which are not antichains and have cardinality less than a given finite value. Let P_n be the direct product of S₁,…, S_n. An asymptotic formula of the maximum size of an h-family in P_n is given, where $\text{h=o(}\text{n}\text{)}$ and n → ∞.     

Constructing graphs with pairs of pseudo-similar vertices

Vertices u and v in the graph G are said to be pseudo-similar if G ? u ? G ? v but no automorphism of G maps u onto v. It is shown that a known procedure for constructing finite graphs with pairs of pseudo-similar vertices actually produces all such graphs. An additional procedure for constructing infinite graphs with pseudo-similar vertices is introduced and it is shown that all such graphs can be obtained by using either this or the first-mentioned method. The corresponding result for pseudo-similar edges is given.     

Planar zero divisor graphs of partially ordered sets

We associate a graph G ^?(P) to a partially ordered set (poset, briefly) with the least element?0, as an undirected graph with vertex set P ^?=P?{0} and, for two distinct vertices x and y, x is adjacent to?y in?G ^?(P) if and only if {x,y} ^? ={0}, where, for a subset?S of?P, S ^? is the set of all elements x∈P with x≦s for all s∈S. We study some basic properties of?G ^?(P). Also, we completely investigate the planarity of?G ^?(P).     

Graphs with three mutually pseudo-similar vertices

Vertices u and v of a graph X are pseudo-similar if X ? u ? X ? v but no automorphism of X maps u to v. We describe a group-theoretic method for constructing graphs with a set of three mutually pseudo-similar vertices. The method is used to construct several examples of such graphs. An algorithm for extending, in a natural way, certain graphs with three mutually pseudo-similar vertices to a graph in which the three vertices are similar is given. The algorithm suggests that no simple characterization of graphs with a set of three mutually pseudo-similar vertices can exist.     

On minimizing jumps for ordered sets

An ordered set P is called K-free if it does not contain a four-element subset {a, b, c, d} such that a < b is the only comparability among these elements. In this paper we present a polynomial algorithm to find the jump number of K-free ordered sets.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

Cores,cutsets and the fixed point property

The purpose of this paper is the analysis and application of the concepts of a core (a pair of chains) and cutset in the fixed point theory for posets. The main results are:

1. (Theorem 3) If P is chain-complete and (*), it contains a cutset S such that every nonempty subset of S has a join or a meet in P, then P has the fixed point property (FPP),
2. (Theorem 5) If P or Q is chain-complete, Q satisfies (*) and both P and Q have the FPP, then P x Q has the FPP.
3. (Theorem 6) Let P or Q be chain-complete and there exist p∈P and a finite sequence f ₁, f ₂, ..., f _n of order-preserving mappings of P into P such that $$\left( {\forall x\varepsilon P} \right)x \leqslant f_1 \left( x \right) \geqslant f_2 \left( x \right) \leqslant \cdots \geqslant f_n \left( x \right) \leqslant p$$ If P and Q have the FPP then P x Q has the FPP.
4. (Theorem 7) If T is an ordered set with the FPP and {P _t :t∈T} is a disjoint family of ordered sets with the FPP then its ordered sum ∪{P _t :t∈T} has the FPP.

     

Fixed point theorems for ordered sets P with P ∖ {a,c} as retract

We prove fixed point theorems for ordered sets P that have a retract with two points less than P and show how they can be used to prove the fixed point property for various well-known and various new ordered sets.     

Sums of sets of lattice points and unimodular coverings of polytopes

If P is a lattice polytope (that is, the convex hull of a finite set of lattice points in \({\mathbf{R}^n}\)), then every sum of h lattice points in P is a lattice point in the h-fold sumset hP. However, a lattice point in the h-fold sumset hP is not necessarily the sum of h lattice points in P. It is proved that if the polytope P is a union of unimodular simplices, then every lattice point in the h-fold sumset hP is the sum of h lattice points in P.     

The jump number of Z-free ordered sets

An ordered set P is called Z-free if it does not contain a four-element subset {a, b, c, d} such that a and c are the only comparabilities among these elements. In this paper we present a polynomial algorithm to find the jump number of finite Z-free ordered sets and that of their duals.     

Normal family and the sequence of omitted functions

Let {fn} be a sequence of meromorphic functions on a plane domain D, whose zeros and poles have multiplicity at least 3. Let {hn} be a sequence of meromorphic functions on D, whose poles are multiple, such that {hn} converges locally uniformly in the spherical metric to a function h which is meromorphic and zero-free on D.If fn≠hn, then {fn} is normal on D.     

On algebras with a generalized implication

We introduce the notion of gi-algebra as a generalization of dual BCK-algebra, and define the notions of strong, commutative and transitive gi-algebra, and then we show that an interval ↑l = {a ∈ P | l ≤ a} in a strong and commutative gi-algebra P is a lattice. Also, we define a congruence relation ～ _D on a transitive gi-algebra P and show that the quotient set P/～ _D is a gi-algebra and a dual BCK-algebra.     

Generalized varieties of sums of powers

Let X ? P^N be an irreducible, non-degenerate variety. The generalized variety of sums of powers V S P_H^X(h) of X is the closure in the Hilbert scheme Hilb_h (X) of the locus parametrizing collections of points {x₁,..., x_h} such that the (h -1)-plane >x₁,..., x_h> passes through a fixed general point p ∈ P^N. When X = V_dⁿ is a Veronese variety we recover the classical variety of sums of powers V S P(F, h) parametrizing additive decompositions of a homogeneous polynomial as powers of linear forms. In this paper we study the birational behavior of V S P_H^X(h). In particular, we show how some birational properties, such as rationality, unirationalityand rational connectedness, of V S P_H^X(h) are inherited from the birational geometry of variety X itself.     

Directed graphs over topological spaces: Some set theoretical aspects

In this paper we shall consider problems of the following type. SupposeG is some set,U is some family of subsests ofG (e.g.G could be the Euclidean plane andU might be the family of all sets of Lebesgue measure zero), andG is any directed graph overG (i.e. any collection of ordered pairs of members ofG) such that for eachg∈G the set {h:<g,h>∈G} belongs to the familyU. How large a setSυG must there exist with the property that (S×S) ∩G=, i.e. such that it is totally disconnected? In many of the cases we shall consider (including the particular example above), the answer will turn out to be independent of the axioms of set theory and will remain so even after adjoining the negation of the continuum hypothesis.     

Ensembles d''articulation d''un graphe γ-critique

We prove that if L is a semimodular lattice of finite length (with least element 0 and greatest element 1) then the partially ordered set L?{0, 1} has the fixed point property if and only if L is not complemented. Moreover, for general lattices L of finite length we consider the relationship of the fixed point property for L?{0, 1} to several other order-theoretic conditions.     

A variation of Menger's theorem for long paths

In this paper we prove a Mengerian theorem for long paths, namely, that if in order to cut every uv-path of length at least n (n ≥ 2), in a diagraph D, we need to remove at least h points, then there exist {$\text{h}\text{(3n ? 5)}$} interior disjoint uv-paths in D of length at least n. Some variations and applications of this theorem are given as well.     

Some remarks on normalized matching

A new class of LYM orders is obtained, and several results about general LYM orders are proved. (1) Let A₁ ? A₂ ? … ? A_r be a chain of subsets of [n] = {l,…,n}. Let 〈a_i〉 and 〈b_i〉 be two nondecreasing sequences with a_i ? b_i for l ? i ? r. Then {X ? [n]: a_i ? | ∩ A_i|? b_i}, ordered by inclusion, is a poset having the LYM property. (2) The smallest regular covering of an LYM order has M(P) chains, where M(P) is the least common multiple of the rank sizes. (3) Every LYM order has a smallest regular covering with at most || ? h(P) classes of distinct chains, where h(P) is the height of P. To obtain (3), we discuss “minimal sets” of covering relations between two adjacent levels of an LYM-order.