A Finite Non-Unit Free Triangle Order

The notion of a free triangle representation of a partially ordered set was first introduced by Josh Laison [4] as a generalization of the ideas of interval and trapezoid representations. A free triangle representation assigns a triangle to each element of a partially ordered set, with all triangles having one vertex on each of two parallel baselines and a third ‘free’ vertex between the two baselines. In a previous paper [1] we presented an example of an infinite non-unit free triangle order. In this paper we use some of the same ideas to construct an example of a finite, albeit more complicated, non-unit free triangle order.The majority of the content in this paper (theorems, proofs, etc.) was prepared before Ken's untimely death in March of 2005.     

Non-Unit Free Triangle Orders

A Free Triangle order is a partially ordered set in which every element can be represented by a triangle. All triangles lie between two parallel baselines, with each triangle intersecting each baseline in exactly one point. Two elements in the partially ordered set are incomparable if and only if their corresponding triangles intersect. A unit free triangle order is one with such a representation in which all triangles have the same area. In this paper, we present an example of a non-unit free triangle order.     

Tube Representations of Ordered Sets

We define the (n,i,f)-tube orders, which include interval orders, trapezoid orders, triangle orders, weak orders, order dimension n, and interval-order-dimension n as special cases. We investigate some basic properties of (n,i,f)-tube orders, and begin classifying them by containment. Mathematics Subject Classifications (2000) 06A06, 05C62.     

Triangle,Parallelogram, and Trapezoid Orders

In his 1998 paper, Ryan classified the sets of unit, proper, and plain trapezoid and parallelogram orders. We extend this classification to include unit, proper, and plain triangle orders. We prove that there are 20 combinations of these properties that give rise to distinct classes of ordered sets, and order these classes by containment.     

Proper and Unit Trapezoid Orders and Graphs

We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.     

ContributionsTree-visibility orders

We introduce a new class of partially ordered sets, called tree-visibility orders, containing interval orders, duals of generalized interval orders and height one orders. We give a characterization of tree-visibility orders by an infinite family of minimal forbidden suborders. Furthermore, we present an efficient recognition algorithm for tree-visibility orders.     

Characterizations of totally ordered sets by their various endomorphisms

We characterize totally ordered sets within the class of all ordered sets containing at least three-element chains using a simple relationship between their isotone transformations and the so called 2-, 3-, 4-endomorphisms which are introduced in the paper. Another characterization of totally ordered sets within the class of ordered sets of a locally finite height with at least four-element chains in terms of the regular semigroup theory is also given.     

Triply Existentially Complete Triangle‐Free Graphs

A triangle‐free graph G is called k‐existentially complete if for every induced k‐vertex subgraph H of G, every extension of H to a ‐vertex triangle‐free graph can be realized by adding another vertex of G to H. Cherlin  11 , 12 asked whether k‐existentially complete triangle‐free graphs exist for every k. Here, we present known and new constructions of 3‐existentially complete triangle‐free graphs.     

On invertibility and zero-augmentability ofN-gon orders

A class of finite partially ordered sets isinvertible if the inverse (dual) of every poset in the class is in the class, and iszero-augmentable if the addition of a new element below all others yields a poset in the class for each member. This paper demonstrates that certain classes of posets that have representations byN-gons in the plane ordered by proper inclusion are neither invertible nor zero-augmentable. AMS subject classification (1980). 06A10.     

On the Polarity and Monopolarity of Graphs

Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle‐free graphs and claw‐free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP‐complete for triangle‐free graphs. We also show that for claw‐free graphs the former is NP‐complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP‐completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw‐free graphs uses a subroutine similar to the well‐known breadth‐first search algorithm and is based on a new structural characterization of monopolar claw‐free graphs, a generalization of one for monopolar line graphs obtained earlier.     

Maximal Induced Matchings in Triangle‐Free Graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n‐vertex graph has at most  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3, 3}. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.     

Geometric Containment Orders: A Survey

A partially ordered set (X, ) is a geometric containment order of a particular type if there is a mapping from X into similarly shaped objects in a finite-dimensional Euclidean space that preserves by proper inclusion. This survey describes most of what is presently known about geometric containment orders. Highlighted shapes include angular regions, convex polygons and circles in the plane, and spheres of all dimensions. Containment orders are also related to incidence orders for vertices, edges and faces of graphs, hypergraphs, planar graphs and convex polytopes. Three measures of poset complexity are featured: order dimension, crossing number, and degrees of freedom.     

特征值问题的预变换方法(I): 杨辉三角阵变换与二阶PDE 特征多项式

本文提出一类求解特征值问题的下三角预变换方法, 目标是通过相似变换后矩阵下三角元素平方和明显减少、且变换后的特征值及其特征向量较易求解, 使变换后的对角线可作为全体特征值很好的一组初值, 其作用如同对于解方程组找到好的预条件子, 加速迭代收敛. 以二阶PDE 数值计算为例,对于以Laplace 方程为代表的特征波向量组及正交多项式组有广泛的应用前景.
杨辉三角是我国古代数学家的一项重要成就. 本文引入杨辉三角矩阵作为预变换子, 给出一般矩阵用杨辉三角矩阵作为左、右预变换子时变为上三角矩阵的充要条件, 给出了元素为行指标二次多项式的两个矩阵类(三对角线阵与五对角线阵) 中特征值何时保持二次多项式的充要条件, 并应用于构造新的二元PDE 正交多项式.     

Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

A tanglegram Kuratowski theorem

A tanglegram consists of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. Tanglegrams are drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines, and the perfect matching inside the strip. If this can be done without any edges crossing, a tanglegram is called planar. We show that every nonplanar tanglegram contains one of two nonplanar 4-leaf tanglegrams as an induced subtanglegram, which parallels Kuratowski's Theorem.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.     

On a tiling problem of R.B. Eggleton

A tiling of the plane with polygonal tiles is said to be strict if any point common to two tiles is a vertex of both or a vertex of neither. A triangle is said to be rational if its sides have rational length. Recently R.B. Eggleton asked if it is possible to strictly tile the plane with rational triangles using precisely one triangle from each congruence class. In this paper we constructively prove the existence of such a tiling by a suitable modification of the technique suggested by Eggleton. The theory of rational points on elliptic curves, in particular, the Nagell-Lutz theorem, plays a crucial role in completing the proof.     

Algebras Defined from Ordered Sets and the Varieties they Generate

We investigate ways of representing ordered sets as algebras and how the order relation is reflected in the algebraic properties of the variety (equational class) generated by these algebras. In particular we consider two different but related methods for constructing an algebra with one binary operation from an arbitrary ordered set with a top element. The two varieties generated by all these algebras are shown to be well-behaved in that they are locally finite, finitely based, and have an equationally definable order relation. We exhibit a bijection between the subdirectly irreducible algebras in each variety and the class of all ordered sets with top element. We determine the structure and cardinality of the free algebra on n-free generators and provide sharp bounds on the number of n-generated algebras in each variety. These enumeration results involve the number of quasi-orders on an n-element set.     

A Characterization of 1-, 2-, 3-, 4-Homomorphisms of Ordered Sets

We characterize totally ordered sets within the class of all ordered sets containing at least four-element chains. We use a simple relationship between their isotone transformations and the so called 1-endomorphism which is introduced in the paper. Later we describe 1-, 2-, 3-, 4-homomorphisms of ordered sets in the language of super strong mappings.     

Catalan numbers,binary trees,and pointed pseudotriangulations

We study connections among structures in commutative algebra, combinatorics, and discrete geometry, introducing an array of numbers, called Borel’s triangle, that arises in counting objects in each area. By defining natural combinatorial bijections between the sets, we prove that Borel’s triangle counts the Betti numbers of certain Borel-fixed ideals, the number of binary trees on a fixed number of vertices with a fixed number of “marked” leaves or branching nodes, and the number of pointed pseudotriangulations of a certain class of planar point configurations.