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,

Official source

https://en.wikipedia.org/wiki/Order_dimension

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 (2)

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 as diverse as mathematical reasoning, combinatorics, disc ...

BIO-369: Randomness and information in biological data

Biology is becoming more and more a data science, as illustrated by the explosion of available genome sequences. This course aims to show how we can make sense of such data and harness it in order to understand biological processes in a quantitative way. ...

Related lectures (7)

Möbius inversion: posets

Covers the Möbius inversion for posets, defining partially ordered sets and explaining the incidence algebra.

Relations and Sequences

Covers relations, sequences, and posets, emphasizing properties like anti-symmetry and transitivity, and introduces arithmetic and geometric progressions.

Equivalence Relations and Partial Orderings

Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.

Graph Chat

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.

Official source

https://en.wikipedia.org/wiki/Order_dimension

About this result

Related courses (2)

CS-101: Advanced information, computation, communication I

BIO-369: Randomness and information in biological data

Related lectures (7)

Möbius inversion: posets

Covers the Möbius inversion for posets, defining partially ordered sets and explaining the incidence algebra.

Relations and Sequences

Covers relations, sequences, and posets, emphasizing properties like anti-symmetry and transitivity, and introduces arithmetic and geometric progressions.

Equivalence Relations and Partial Orderings

Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.

Related publications (4)

Synchronization on Circles and Spheres with Nonlinear Interactions

We consider the dynamics of n points on a sphere in ℝ^d (d ≥ 2) which attract each other according to a function φ of their inner products. When φ is linear (φ(t) = t), the points converge to a common value (i.e., synchronize) in various connectivity scenarios; this is part of classical work on Kuramoto oscillator networks. When φ is exponential (φ(t) = e^(βt)), these dynamics correspond to a limit of how idealized transformers process data, as described by Geshkovski et al. (Bull. Amer. Math. Soc., 62 (202

Society for Industrial and Applied Mathematics2026

Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications

In 2006, Marcus and Tardos proved that if are cyclic orders on some subsets of a set of symbols such that the common elements of any two distinct orders and appear in reversed cyclic order in and , then . This result is tight up to the logarithmic factor and has since become an important tool in Discrete Geometry. In this paper, we improve this to the optimal bound . In fact, we prove the following more general result. We show that if are linear orders on some subsets of a set of symbols such that no three

Wiley2025

Counterexamples to a fiber theorem

We exhibit a counterexample to a fiber theorem stated by F. Fumagalli [J. Algebra 283 (2) (2005), 639-654] and show how it affects the rest of Fumagalli's paper. As a consequence, whether the poset A_p(G) is homotopy equivalent to a wedge of spheres for an ...

2009

Related concepts (3)

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.

Related notebooks (1)

Exploring the Karplus-Strong Algorithm for Sound Synthesis

The Karplus-Strong Algorithm[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

The Karplus-Strong algorithm is a simple method to generate synthetic sounds with arbitrary pitch. In this notebook we will explore a few variations of the method to illustrate some basic notions of discrete-time signal processing. In [1]: %matplotlib inline import matplotlib import matplotlib.pyplot as plt import numpy as np import IPython In [2]: plt.rcParams["figure.figsize"]