Semi-graphoids interpreted as collections of posets.

Abstract: Semi-graphoids are discrete structures introduced in context of probabilistic reasoning. Particular structural semi-graphoids correspond to the non-empty faces of the cone of tight polymatroids. A result will be presented that any semi-graphoid over a finite non-empty variable set N can be viewed as a collection of posets (= partial orderings) on N. To this end, a semi-graphoid is first identified with a particular subgraph of the so-called permutohedral graph, whose nodes are enumerations (= total orderings) of N. The components of this semi-graphoidal subgraph appear to be special geodetically convex sets in the permutohedral graph and, for this reason, each of these components uniquely corresponds to a poset on N. We also mention geometrical interpretation of finite posets in terms of so-called braid cones.

The presentation is based on the paper Semi-graphoids viewed as collections of posets. To appear in Proceedings of the 21th conference IPMU 2026 (B. Vantaggi et al. eds), Springer.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.