No Arabic abstract
We define toric partial orders, corresponding to regions of graphic toric hyperplane arrangements, just as ordinary partial orders correspond to regions of graphic hyperplane arrangements. Combinatorially, toric posets correspond to finite posets under the equivalence relation generated by converting minimal elements into maximal elements, or sources into sinks. We derive toric analogues for several features of ordinary partial orders, such as chains, antichains, transitivity, Hasse diagrams, linear extensions, and total orders.
Since Cho and Kim (2005) showed that the competition graph of a doubly partial order is an interval graph, it has been actively studied whether or not the same phenomenon occurs for other variants of competition graph and interesting results have been obtained. Continuing in the same spirit, we study the competition hypergraph, an interesting variant of the competition graph, of a doubly partial order. Though it turns out that the competition hypergraph of a doubly partial order is not always interval, we completely characterize the competition hypergraphs of doubly partial orders which are interval.
An interval $k$-graph is the intersection graph of a family $mathcal{I}$ of intervals of the real line partitioned into at most $k$ classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we discuss the interval $k$-graphs that are the incomparability graphs of orders; i.e., cocomparability interval $k$-graphs or interval $k$-orders. Interval $2$-orders have been characterized in many ways, but we show that analogous characterizations do not carry over to interval $k$-orders, for $k > 2$. We describe the structure of interval $k$-orders, for any $k$, characterize the interval $3$-orders (cocomparability interval $3$-graphs) via one forbidden suborder (subgraph), and state a conjecture for interval $k$-orders (any $k$) that would characterize them via two forbidden suborders.
We consider the Graver basis, the universal Groebner basis, a Markov basis and the set of the circuits of a toric ideal. Let $A, B$ be any two of these bases such that $A ot subset B$, we prove that there is no polynomial on the size or on the maximal degree of the elements of $B$ which bounds the size or the maximal degree of the elements of $A$ correspondingly.
Toric posets are cyclic analogues of finite posets. They can be viewed combinatorially as equivalence classes of acyclic orientations generated by converting sources into sinks, or geometrically as chambers of toric graphic hyperplane arrangements. In this paper we study toric intervals, morphisms, and order ideals, and we provide a connection to cyclic reducibility and conjugacy in Coxeter groups.
We introduce the notion of tau-like partial order, where tau is one of the linear order types omega, omega*, omega+omega*, and zeta. For example, being omega-like means that every element has finitely many predecessors, while being zeta-like means that every interval is finite. We consider statements of the form any tau-like partial order has a tau-like linear extension and any tau-like partial order is embeddable into tau (when tau is zeta this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to BSigma^0_2 or to ACA_0 over the usual base system RCA_0.