Boolean dimension of boolean lattices
Time: 14:00 -- Location: LRI, 445
summary: Partially ordered sets (or posets for short) are structures that arise naturally in mathematics in the study of binary relations between objects. A poset consists of a ground set -- a set of elements -- and a partial order among them, and are usually visualled with directed acyclic graphs (DAGs). Indeed, the vertices can represent our elements, and the arcs can represent the partial order. A way to measure the complexity of the representation of a poset is through the (Dushnik-Miller) dimension. Geometrically, it is the minimum number of dimensions needed so that each element can be mapped to a vector where the partial order is exactly the coefficient-wise order on the vectors. More formally, it is the minimum number of linear extensions -- total orders on the ground set respecting the partial order -- such that the intersection of their binary relations is exactly our partial order. A set of linear extensions with such a property is called a realizer. From the perspective of a decomposition, a poset of dimension d can be "decomposed" into d linear extensions. This measure has been well-studied in poset theory and is one of its main axes of research.
From a computer scientist's point of view, the complexity of representing a poset with total orders can also be seen as the amount of information -- the number of orders -- needed to be able to answer the query 'is x less than y?' for any pair of elements x, y. This is the boolean dimension It generalizes the notion of Dushnik-Miller dimension, i.e., 'is x less than y in P?' is equivalent to 'is x less than y in every linear extension of a realizer of P?', so it is an upper bound on the boolean dimension. Similarly, a boolean realizer is a set of total orders that allows us to correctly answer every possible query.
The study of boolean dimension is especially interesting from the perspective of graph theory. Every directed graph has a natural underlying poset. More precisely, if we contract the strongly connected components of a digraph, then the resulting DAG defines a natural poset. From this viewpoint, the query 'is x less than y?' is the same as 'does there exist a directed path from x to y?'. Labeling the vertices in such a way that we can answer this reachability query efficiently is at the heart of research on reachability labeling schemes in graphs. Having a small boolean realizer gives us an efficient algorithm to answer reachability queries.
In general, dimension and boolean dimension can be arbitrarily far apart. Therefore, classes of posets for which these two measures are close together are of particular interest. A well-known class of posets for which dimension and boolean dimension were suspected to be the same is the class of boolean lattices -- the poset with the inclusion order on powersets of 1, 2, ..., n. In this seminar, we will detail the research on dimension in poset theory, how it relates to graph theory, and present new results on the boolean dimension of boolean lattices.