Concept

Order dimension

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions. That is, An alternative definition of order dimension is the minimal number of total orders such that P embeds into their product with componentwise ordering i.e. if and only if for all i (, ). A family of linear orders on X is called a realizer of a poset P = (X,

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (1)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Related lectures (7)
Equivalence Relations and Partial Orderings
Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.
Relations and Sequences
Covers relations, sequences, and posets, emphasizing properties like anti-symmetry and transitivity, and introduces arithmetic and geometric progressions.
Partial Ordering: Relations, Sequences, Summation
Explores partial orderings, divisibility relations, lattices, lexicographic ordering, comparability, and total orderings.
Show more
Related publications (9)

A simple proof for a forbidden subposet problem

Abhishek Methuku

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1)
ELECTRONIC JOURNAL OF COMBINATORICS2020

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form min{f(x):Ax=b, lxu, xZn}\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}, where AZm×nA \in \Z^{m \times n}, bZmb \in \Z^m, l,uZnl,u \in \Z^n, and f:ZnZf: \Z^n \rightarrow \Z is a separable convex objective function. The problem o ...
EPFL2020

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
CAMBRIDGE UNIV PRESS2020
Show more
Related concepts (4)
Interval order
In mathematics, especially order theory, the interval order for a collection of intervals on the real line is the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2. More formally, a countable poset is an interval order if and only if there exists a bijection from to a set of real intervals, so , such that for any we have in exactly when .
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. A partial order is a reflexive, transitive and antisymmetric relation.
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.