Configured spaces and their Möbius polynomials
Samy Abbes · 2025
Read Configured spaces and their Möbius polynomials by Samy Abbes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-12795.txt.
Introduction
Samy Abbes studies configured spaces and their Möbius polynomials in a 2025 paper. Start with a pattern of dependencies among events, drawn as a hypergraph, and ask for the canonical probability space that realizes exactly that pattern.
Abbes calls such a hypergraph a configuration when events outside the independence pattern must exclude each other. Giving every event the same positive chance turns the question into algebra: a family of polynomials, kin to graph independence polynomials, counts the valid assignments. The graph case was already settled; the general hypergraph case was open. A new formula for the polynomial's derivative yields existence and uniqueness of the best shared probability, the one making the events cover the most total chance.
Catalog record
| CREATOR | Samy Abbes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-12795
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Configured spaces and their Möbius polynomials Samy Abbes Abstract An arbitrary dependence structure between a finite family of events of a probability space defines a hypergraph structure. We study the converse operation, starting from a hypergraph structure, to determine a canonical probability space with events indexed by the vertices and that satisfy the prescribed dependence structure; we also require that events that are not mutually independent must be mutually exclusive. Such a hypergraph structure, we call a configuration. Requiring furthermore that all events are given the same positive probability t t , converts this problem to the study of a family of Möbius polynomials, which we call the relative Möbius polynomials (or independence polynomial) of the configuration. This study was very much already complete in the case where the configuration actually derives from a graph structure, but remained open in the general case. We show the existence and uniqueness of an optimal real t t , optimal in the sense that the events cover a subset of maximal probability. We base our study on a new formula for the derivative of the Möbius polynomial. Keywords: hypergraph, Möbius polynomial, independence polynomial \acinq \aquatre 1 Introduction Let (\Omega,\mathcal{F},\mathbb{P}) be a probability space, and let (a_{1},\dots,a_{n}) be a family of events, all of them of positive probability, and with the following property: for every subset A\subseteq[n]=\{1,\dots,n\} , either the family (a_{i})_{i\in A} is exclusive modulo zero, ie, \mathbb{P}\bigl(\bigcap_{i\in A}a_{i}\bigr)=0 , or it is an independent family of events, ie, \mathbb{P}(\bigcap_{i\in B}a_{i})=\prod_{i\in B}\mathbb{P}(a_{i}) for every subset B\subseteq A . This whole data makes what we call a configured space . This configured space induces a hypergraph structure on V=[n] , namely it defines the two families \mathcal{I}=\{x\in\mathcal{P}(V)\tq\text{$x$ is independent}\} and \mathcal{D}=\{x\in\mathcal{P}(V)\tq\text{$x$ is mutually exclusive}\} . Let \leq denote the inclusion order on \mathcal{P}(V) . Obviously, \mathcal{I} is \leq -downward closed, whereas \mathcal{D} is \leq -upward closed, and \mathcal{I} contains all singletons. Conversely, consider a hypergraph structure (V,\mathcal{I}) where V is a finite set of vertices, and \mathcal{I} is a family of subsets of V , such that \mathcal{I} contains all singletons \{a\} for a\in V and is downward closed with respect to inclusion in \mathcal{P}(V) . Put also \mathcal{D}=\mathcal{P}(V)\setminus\mathcal{I} . The data (V,\mathcal{I},\mathcal{D}) forms what we call a configuration . A first question is the existence of a probability space (\Omega,\mathcal{F},\mathbb{P}) and of a mapping \varphi:V\to\mathcal{F} with the following properties: 1) \mathbb{P}(\varphi(a))>0 for all a\in V ; and 2) \varphi(x) is an independent family of events if x\in\mathcal{I} ; and 3) \varphi(x) is mutually exclusive modulo zero if x\in\mathcal{D} . A second question consists in replacing the first item above, ie, \mathbb{P}(\varphi(a))>0 for all a\in V , by the requirement that \mathbb{P}(\varphi(a))=t for all a\in V and for some positive real t . Finally, a third question consists in adding the following requirement: the whole collection of events (\varphi(a))_{a\in V} forms a covering modulo zero of \Omega , ie, \mathbb{P}(\bigcup_{a\in V}\varphi(a))=1 . Although this topic does not seem to have been systematically explored so far, it turns out that the above questions have been given an answer for some particular cases, namely when the abstract configuration (V,\mathcal{I},\mathcal{D}) is induced by a graph (V,D) , in the sense that \mathcal{I} is the set of independence cliques of the graph. In [ 9 ] , Shearer uses this construction to establish optimal bounds for the Lovász Local Lemma; many works have been inspired from Shearer’s paper, the main theme being to establish optimal regions where the independence polynomials of graphs with bounded degree do not vanish. Extensions of results in the same vein have been carried on to hypergraphs [ 5 ] . The present work departs from this vein of research as we are interested in studying precise independence polynomials, and not in obtaining general results valid for hypergraphs of a given maximal degree. Furthermore, our probabilistic motivations narrows our study of the independence polynomials on the negative part of the line only, and more precisely on the (-1,0) interval only. Actually, the Möbius polynomials \mu(t) that we study are related to the independence polynomials \theta(t) by \mu(t)=\theta(-t) , and our study related to the Möbius polynomials is thus located on the interval (0,1) . Here is how the Möbius polynomial appears, and this will also introduce the major difference between the general case and the case of graphs. Assume given a configured space (\Omega,\mathcal{F},\mathbb{P}) with configuration (V,\mathcal{I},\mathcal{D}) and such that \mathbb{P}(a)=t>0 for all a\in V ; for simplicity, we drop the mapping \varphi , and simply identify vertices with the events of \Omega that they represent. Let the rest be defined by R(t)=1-\mathbb{P}\bigl(\bigcup_{a\in V}a) , so that the configuration forms a covering modulo zero if and only if R(t)=0 . By the inclusion-exclusion principle, we have: \displaystyle R(t)=1-\sum_{x\in\mathcal{P}(V),\ x\neq\emptyset}(-1)^{|x|+1}\mathbb{P}\Bigl(\bigcap x\Bigr) (1) Now every non empty subset x\in\mathcal{P}(V) is either a family of independent events, if x\in\mathcal{I} , in which case \mathbb{P}\bigl(\bigcap x)=\prod_{a\in x}\mathbb{P}(a)=t^{|x|} ; or a family of mutually exclusive events modulo zero, if x\in\mathcal{D} , in which case \mathbb{P}(\bigcap x)=0 . Hence: \displaystyle R(t)=\sum_{x\in\mathcal{I}}(-1)^{|x|}t^{|x|} (2) Therefore, a necessary condition for the existence of t satisfying our requirements is that R(t)\geq 0 , where R(t) is now the polynomial defined by ( 2 ), and which only depends on the abstract configuration. This polynomial is the Möbius polynomial of the configuration. R(0)=1 hence R>0 in a neighborhood of 0 , but we shall see that the condition R(t)\geq 0 is not sufficient for t to define a valid probability \mathbb{P}_{t} , ie, satisfying \mathbb{P}_{t}(a)=t and respecting the independence and exclusion conditions of the abstract configuration. Nevertheless, we shall see that there is indeed an interval [0,\delta] for which all t\in(0,\delta] define a valid configured space with \mathbb{P}_{t}(a)=t for all a\in V . A secondary question that arises is the monotony of R(t) on [0,\delta] . Of course, as a polynomial of arbitrary degree, it has no reason to be monotonic on the interval (0,1) . From the probabilistic point of view, 1-R(t) is the probability of the union \bigcup V . When t increases, every individual probability \mathbb{P}_{t}(a)=t increases, but this is not sufficient in general to guarantee that t\mapsto\mathbb{P}_{t}(\bigcup V) increases, and thus that t\mapsto R(t) decreases. Nevertheless, we shall prove this fact indeed, and for this we give an expression for the derivative of R(t) which does not seem to have been noted so far, and which is of interest on its own. As a result, if the configuration can define a covering of its configured space for some real t>0 , then it must be the case that t=\delta and that R(\delta)=0 . Now if we examine the case of a configuration induced by a graph, several questions already have an answer. The major advantage in this situation is that the polynomial R(t) has a combinatorial interpretation, as follows. Let \mathcal{M} be the trace monoid generated by (V,D) . That is, introducing the binary relation I=(V\times V)\setminus D , \mathcal{M} is the monoid defined by generators and relations by: \mathcal{M}=\langle V\ |\ \forall(a,b)\in I\quad ab=ba\rangle , and let G(t)=\sum_{x\in\mathcal{M}}t^{|x|} be the generating series of \mathcal{M} . Then a result of Cartier and Foata in [ 2 ] is the following identity: