pith. sign in

arxiv: 2605.03556 · v1 · submitted 2026-05-05 · 💻 cs.CC · math.CO· math.PR

Optimal Union Probability Interval Is NP-Hard

Petteri Kaski , Heikki Mannila , Chandra Kanta Mohapatra This is my paper

Pith reviewed 2026-05-09 16:14 UTC · model grok-4.3

classification 💻 cs.CC math.COmath.PR
keywords NP-hardunion probabilityBoole problemHailperin linear programVenn diagram atomspolytope projectionprobabilistic logiccomputational complexity
0
0 comments X

The pith

Computing the tightest bounds on the probability of a union of events is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that determining the optimal interval for the probability of the union of events, based on given probabilities of some of their intersections, is NP-hard. This addresses a problem originating from Boole in 1854 and clarifies limitations in probabilistic logic and geometric probability models. A reader would care because it shows that exact computation of these bounds cannot be efficient in general, affecting how we reason about uncertain events with incomplete information.

Core claim

The central discovery is that the problem of computing the optimal (narrowest) interval for the probability of the union, phrased via coordinate projections of the polytope defined by Hailperin's linear program on the atoms of the Venn diagram, is NP-hard. This resolves the gap noted by Pitowsky and Boros et al. by establishing intractability through a polynomial-time reduction.

What carries the argument

Coordinate projections of the elementary polytope arising from Hailperin's linear program on Venn-diagram atoms, which encodes the feasible probability assignments and allows reduction to show hardness.

If this is right

  • The optimal union probability interval cannot be computed in polynomial time unless P equals NP.
  • This intractability holds even for the basic disjunction case in Boole's problem.
  • Similar hardness may apply to other logical formulas in probabilistic logic.
  • Algorithms for approximating the bounds or handling restricted cases remain relevant.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical systems for uncertain reasoning may need to rely on approximations or heuristics rather than exact bounds.
  • This connects to challenges in marginal polytopes for graphical models where similar projection problems arise.
  • Future work could identify tractable subclasses based on the structure of the given intersections.

Load-bearing premise

The formulation using coordinate projections of the polytope from Hailperin's program on Venn atoms accurately represents the original problem and allows a valid reduction from a known NP-hard problem.

What would settle it

A polynomial-time algorithm that, for any set of events and given intersection probabilities, computes the exact tightest lower and upper bounds on the union probability would falsify the NP-hardness claim.

read the original abstract

A problem dating back to Boole [Laws of Thought, Walton & Maberly,1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343--359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif.\ Intell.\ 28 (1986) 71--87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J.Complexity 4 (1988) 1--11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found.\ Trends Mach.\ Learn. 1 (2008) 1--305]. This paper (i) describes the pertinent geometry of Boole's problem via coordinate projections of an elementary polytope arising essentially from Hailperin's linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math.\ Programming 50 (1991) 395--414] and Boros et al. [Math.\ Oper.\ Res. 39 (2014) 1311--1329 and 51 (2026) 134--148].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper describes the geometry of Boole's classical problem of bounding the probability of a finite union of events given probabilities of selected intersections, modeling it via coordinate projections of the polytope arising from Hailperin's linear program on Venn-diagram atoms. It then proves that computing the tightest lower and upper bounds on this union probability is NP-hard, addressing a gap noted by Pitowsky and Boros et al.

Significance. If the reduction is valid, the result resolves an open complexity question in probabilistic logic and polyhedral combinatorics, with clear connections to cut/correlation polytopes and marginal polytopes. The geometric projection approach is a constructive contribution that clarifies the feasible region, and the use of a standard Karp reduction from a known NP-hard problem (such as PSAT) is a strength when fully detailed.

major comments (1)
  1. [NP-hardness proof] The NP-hardness claim rests on a polynomial-time reduction that maps instances of a known NP-hard problem to instances of computing the optimal union interval. This reduction is realized via the coordinate projection of the Hailperin atom LP. The manuscript must explicitly verify that the projected polytope exactly reproduces the feasible marginals of the original Boole problem (i.e., neither adds spurious constraints nor omits realizability conditions that would change the optimal [L,U] interval). Without this verification the reduction's validity cannot be confirmed.
minor comments (1)
  1. The abstract and introduction could state the main theorem (including the precise source problem for the reduction) more explicitly and earlier to aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and for identifying the need for greater explicitness in the NP-hardness argument. We address the major comment below.

read point-by-point responses

  1. Referee: [NP-hardness proof] The NP-hardness claim rests on a polynomial-time reduction that maps instances of a known NP-hard problem to instances of computing the optimal union interval. This reduction is realized via the coordinate projection of the Hailperin atom LP. The manuscript must explicitly verify that the projected polytope exactly reproduces the feasible marginals of the original Boole problem (i.e., neither adds spurious constraints nor omits realizability conditions that would change the optimal [L,U] interval). Without this verification the reduction's validity cannot be confirmed.

    Authors: We agree that an explicit verification strengthens the presentation. By construction, the Hailperin atom polytope is the probability simplex on the 2^n atoms (nonnegative variables summing to 1), which encodes every possible joint distribution on the events. The coordinate projection onto the subspace spanned by the given intersection probabilities together with the union probability therefore yields precisely the marginal polytope consisting of all realizable marginal vectors. No spurious constraints are added because the only inequalities in the atom model are nonnegativity and normalization; these are inherited by the projection. Conversely, no realizability conditions are omitted: every point in the projected polytope is the image of some atom vector and hence corresponds to a valid probability measure, while every feasible marginal assignment in Boole's problem extends to some atom vector by definition of the atoms. The reduction therefore maps to instances whose optimal [L,U] values coincide exactly with those of the original problem. In the revised manuscript we will insert a short dedicated paragraph (or subsection) immediately after the definition of the projected polytope that states this equivalence formally, including the two directions of the argument above and a reference to the fact that this construction is the standard marginal polytope for the selected events. revision: yes

Circularity Check

0 steps flagged

No circularity: standard NP-hardness reduction via Hailperin LP projection

full rationale

The paper establishes NP-hardness of the optimal union probability interval by a polynomial-time Karp reduction from known NP-hard problems (e.g., PSAT) to the coordinate-projection formulation of the Hailperin atom LP. This is a conventional complexity argument relying on external results about cut polytopes and marginal polytopes; no self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain. The geometry description via projections is used to define the target problem but does not reduce the hardness claim to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard geometric formulation of the problem as linear programming over Venn-diagram atoms and on the definition of NP-hardness via polynomial reductions; no new entities or fitted parameters are introduced.

axioms (2)
  • domain assumption The union probability bounds are given by coordinate projections of the polytope arising from Hailperin's linear program on the atoms of the Venn diagram.
    This is the geometric model used to phrase the problem.
  • standard math NP-hardness is established by polynomial-time reduction from a known NP-complete problem.
    Standard definition in computational complexity.

pith-pipeline@v0.9.0 · 5642 in / 1221 out tokens · 65026 ms · 2026-05-09T16:14:08.884902+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

74 extracted references · 53 canonical work pages

  1. [1]

    Aboulker, S

    P. Aboulker, S. Fiorini, T. Huynh, M. Macchia, and J. Seif, Extension complexity of the corre- lation polytope,Operations Research Letters47 (2019), 47–51. [doi:10.1016/j.orl.2018.12.001]. 7

    work page doi:10.1016/j.orl.2018.12.001 2019

  2. [2]

    Agrawal, T

    R. Agrawal, T. Imielinski, and A. N. Swami, Mining association rules between sets of items in large databases, inProceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, May 26-28, 1993(P. Buneman and S. Jajodia, Eds.). ACM Press, 1993, pp. 207–216. [doi:10.1145/170035.170072]. 6 14

    work page doi:10.1145/170035.170072 1993

  3. [3]

    Agrawal, H

    R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo, Fast discovery of associa- tion rules, inAdvances in Knowledge Discovery and Data Mining(U. M. Fayyad, G. Piatetsky- Shapiro, P. Smyth, and R. Uthurusamy, Eds.), AAAI/MIT Press, 1996, pp. 307–328. 7

    1996

  4. [4]

    Agrawal and R

    R. Agrawal and R. Srikant, Fast algorithms for mining association rules in large databases, in VLDB’94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile(J. B. Bocca, M. Jarke, and C. Zaniolo, Eds.). Morgan Kaufmann, 1994, pp. 487–499. 6

    1994

  5. [5]

    Barvinok, Computing the probability of intersection, arXiv (math.PR) preprint 2507.10329,

    A. Barvinok, Computing the probability of intersection, arXiv (math.PR) preprint 2507.10329,

    work page arXiv

  6. [6]

    [doi:10.48550/arXiv.2507.10329]. 6

    work page doi:10.48550/arxiv.2507.10329

  7. [7]

    L. M. J. Bazzi, Polylogarithmic independence can fool DNF formulas,SIAM J. Comput.38 (2009), 2220–2272. [doi:10.1137/070691954]. 6

    work page doi:10.1137/070691954 2009

  8. [8]

    Bj¨ orklund, T

    A. Bj¨ orklund, T. Husfeldt, and M. Koivisto, Set partitioning via inclusion-exclusion,SIAM J. Comput.39 (2009), 546–563. [doi:10.1137/070683933]. 6

    work page doi:10.1137/070683933 2009

  9. [9]

    C. E. Bonferroni. Teoria statistica delle classi e calcolo delle probabilit` a. (Pubbl. d. R. Ist. Super. di Sci. Econom. e Commerciali di Firenze. 8) Firenze: Libr. Internaz. Seeber. 62 S.,

  10. [10]

    Boole,An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, Walton and Maberly, London, 1854

    G. Boole,An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, Walton and Maberly, London, 1854. [doi:10.5962/bhl.title.29413]. 2

    work page doi:10.5962/bhl.title.29413

  11. [11]

    Boros and J

    E. Boros and J. Lee, Boole’s probability bounding problem, linear programming aggregations, and nonnegative quadratic pseudo-Boolean functions,Math. Oper. Res.51 (2026), 134–148. [doi:10.1287/moor.2023.0019]. 3

    work page doi:10.1287/moor.2023.0019 2026

  12. [12]

    Boros and A

    E. Boros and A. Pr´ ekopa, Closed form two-sided bounds for probabilities that at leastrand ex- actlyrout ofnevents occur,Math. Oper. Res.14 (1989), 317–342. [doi:10.1287/moor.14.2.317]. 6

    work page doi:10.1287/moor.14.2.317 1989

  13. [13]

    Boros, A

    E. Boros, A. Scozzari, F. Tardella, and P. Veneziani, Polynomially computable bounds for the probability of the union of events,Math. Oper. Res.39 (2014), 1311–1329. [doi:10.1287/moor.2014.0657]. 3

    work page doi:10.1287/moor.2014.0657 2014

  14. [14]

    Braverman, Polylogarithmic independence fools AC 0 circuits,J

    M. Braverman, Polylogarithmic independence fools AC 0 circuits,J. ACM57 (2010), Art. 28,

    2010

  15. [15]

    [doi:10.1145/1754399.1754401]. 6

    work page doi:10.1145/1754399.1754401

  16. [16]

    de Caen, A lower bound on the probability of a union,Discrete Math.169 (1997), 217–220

    D. de Caen, A lower bound on the probability of a union,Discrete Math.169 (1997), 217–220. [doi:10.1016/S0012-365X(96)00107-0]. 6

    work page doi:10.1016/s0012-365x(96)00107-0 1997

  17. [17]

    K. L. Chung and P. Erd¨ os, On the application of the Borel-Cantelli lemma,Trans. Amer. Math. Soc.72 (1952), 179–186. [doi:10.2307/1990661]. 6

    work page doi:10.2307/1990661 1952

  18. [18]

    , Will, C.: The industrial ontologies foundry proof-of-concept project

    M. Cygan, F. V. Fomin, L. u. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,Parameterized Algorithms, Springer, Cham, 2015. [doi:10.1007/978-3-319- 21275-3]. 6 15

    work page doi:10.1007/978-3-319- 2015

  19. [19]

    D. A. Dawson and D. Sankoff, An inequality for probabilities,Proc. Amer. Math. Soc.18 (1967), 504–507. [doi:10.2307/2035487]. 6

    work page doi:10.2307/2035487 1967

  20. [20]

    M. M. Deza and M. Laurent,Geometry of Cuts and Metrics, Springer-Verlag, Berlin, 1997. [doi:10.1007/978-3-642-04295-9]. 3, 4, 5

    work page doi:10.1007/978-3-642-04295-9 1997

  21. [21]

    Dohmen,Improved Bonferroni Inequalities via Abstract Tubes, Springer-Verlag, Berlin,

    K. Dohmen,Improved Bonferroni Inequalities via Abstract Tubes, Springer-Verlag, Berlin,

  22. [22]

    [doi:10.1007/b13785]

    Inequalities and identities of inclusion-exclusion type. [doi:10.1007/b13785]. 6

    work page doi:10.1007/b13785

  23. [23]

    Erd˝ os and L

    P. Erd˝ os and L. Lov´ asz, Problems and results on 3-chromatic hypergraphs and some related questions, inInfinite and Finite Sets (Colloq., Keszthely, 1973), North-Holland, Amsterdam, 1975, pp. 609–627. 6

    1973

  24. [24]

    F. V. Fomin and D. Kratsch,Exact Exponential Algorithms, Springer, Heidelberg, 2010. [doi:10.1007/978-3-642-16533-7]. 6

    work page doi:10.1007/978-3-642-16533-7 2010

  25. [25]

    A. N. Frolov, Bounds for probabilities of unions of events and the Borel-Cantelli lemma,Statist. Probab. Lett.82 (2012), 2189–2197. [doi:10.1016/j.spl.2012.08.002]. 6

    work page doi:10.1016/j.spl.2012.08.002 2012

  26. [26]

    Fr´ echet,Les probabilit´ es associ´ ees ` a un syst` eme d’´ ev´ enements compatibles et d´ ependants, Hermann, Paris, 1940

    M. Fr´ echet,Les probabilit´ es associ´ ees ` a un syst` eme d’´ ev´ enements compatibles et d´ ependants, Hermann, Paris, 1940. 2

    1940

  27. [27]

    Fr´ echet,Les probabilit´ es associ´ ees ` a un syst` eme d’´ ev´ enements compatibles et d´ ependants, Hermann, Paris, 1943

    M. Fr´ echet,Les probabilit´ es associ´ ees ` a un syst` eme d’´ ev´ enements compatibles et d´ ependants, Hermann, Paris, 1943. 2

    1943

  28. [28]

    Galambos, Bonferroni inequalities,The Annals of Probability5 (1977), 577–581

    J. Galambos, Bonferroni inequalities,The Annals of Probability5 (1977), 577–581. [doi:10.1214/aop/1176995765]. 6

    work page doi:10.1214/aop/1176995765 1977

  29. [29]

    Galambos and R

    J. Galambos and R. Mucci, Inequalities for linear combinations of binomial moments,Publi- cationes Mathematicae Debrecen27 (1980), 263–268. [doi:10.5486/pmd.1980.27.3-4.09]. 6

    work page doi:10.5486/pmd.1980.27.3-4.09 1980

  30. [30]

    Galambos and I

    J. Galambos and I. Simonelli,Bonferroni-Type Inequalities with Applications, Springer-Verlag, New York, 1996. 6

    1996

  31. [31]

    Gallot, A bound for the maximum of a number of random variables,J

    S. Gallot, A bound for the maximum of a number of random variables,J. Appl. Probability3 (1966), 556–558. [doi:10.2307/3212139]. 6

    work page doi:10.2307/3212139 1966

  32. [32]

    Georgakopoulos, D

    G. Georgakopoulos, D. Kavvadias, and C. H. Papadimitriou, Probabilistic satisfiability,J. Complexity4 (1988), 1–11. [doi:10.1016/0885-064X(88)90006-4]. 4

    work page doi:10.1016/0885-064x(88)90006-4 1988

  33. [33]

    Combinatorica1(2), 169–197 (Jun 1981),http://link.springer.com/10.1007/BF02579273

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica1 (1981), 169–197. [doi:10.1007/BF02579273]. 5

    work page doi:10.1007/bf02579273 1981

  34. [34]

    Geometric algorithms and combinatorial optimization , SERIES =

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver,Geometric Algorithms and Combinatorial Opti- mization, second ed., Springer-Verlag, Berlin, 1993. [doi:10.1007/978-3-642-78240-4]. 5, 10, 14

    work page doi:10.1007/978-3-642-78240-4 1993

  35. [35]

    Hailperin, Best possible inequalities for the probability of a logical function of events,Amer

    T. Hailperin, Best possible inequalities for the probability of a logical function of events,Amer. Math. Monthly72 (1965), 343–359. [doi:10.2307/2313491]. 2, 5, 6 16

    work page doi:10.2307/2313491 1965

  36. [36]

    Hailperin,Sentential Probability Logic, Lehigh University Press, Bethlehem, PA; Associ- ated University Presses, London, 1996

    T. Hailperin,Sentential Probability Logic, Lehigh University Press, Bethlehem, PA; Associ- ated University Presses, London, 1996. Origins, development, current status, and technical applications. 6

    1996

  37. [37]

    Hunter, An upper bound for the probability of a union,Journal of Applied Probability13 (1976), 597–603

    D. Hunter, An upper bound for the probability of a union,Journal of Applied Probability13 (1976), 597–603. [doi:10.1017/s0021900200104164]. 6

    work page doi:10.1017/s0021900200104164 1976

  38. [38]

    Jaeger, Automatic derivation of probabilistic inference rules,International Journal of Ap- proximate Reasoning28 (2001), 1–22

    M. Jaeger, Automatic derivation of probabilistic inference rules,International Journal of Ap- proximate Reasoning28 (2001), 1–22. [doi:10.1016/S0888-613X(01)00044-5]. 6

    work page doi:10.1016/s0888-613x(01)00044-5 2001

  39. [39]

    Jaumard, P

    B. Jaumard, P. Hansen, and M. P. de Arag˜ ao, Column generation methods for probabilistic logic,INFORMS J. Comput.3 (1991), 135–148. [doi:10.1287/IJOC.3.2.135]. 3, 5

    work page doi:10.1287/ijoc.3.2.135 1991

  40. [40]

    J. Kahn, N. Linial, and A. Samorodnitsky, Inclusion-exclusion: exact and approximate,Com- binatorica16 (1996), 465–477. [doi:10.1007/BF01271266]. 6

    work page doi:10.1007/bf01271266 1996

  41. [41]

    D. J. Kavvadias and C. H. Papadimitriou, A linear programming approach to reasoning about probabilities,Ann. Math. Artif. Intell.1 (1990), 189–205. [doi:10.1007/BF01531078]. 4, 5

    work page doi:10.1007/bf01531078 1990

  42. [42]

    Klein and K

    A. Klein and K. Metsch, On approximate inclusion-exclusion,Innov. Incidence Geom.6/7 (2007/08), 249–270. 6

    2007

  43. [43]

    E. G. Kounias, Bounds for the probability of a union, with applications,Ann. Math. Statist. 39 (1968), 2154–2158. [doi:10.1214/aoms/1177698049]. 6

    work page doi:10.1214/aoms/1177698049 1968

  44. [44]

    Kounias and J

    S. Kounias and J. Marin, Best linear Bonferroni bounds,SIAM J. Appl. Math.30 (1976), 307–323. [doi:10.1137/0130031]. 6

    work page doi:10.1137/0130031 1976

  45. [45]

    H. Kuai, F. Alajaji, and G. Takahara, A lower bound on the probability of a finite union of events,Discrete Math.215 (2000), 147–158. [doi:10.1016/S0012-365X(99)00246-0]. 6

    work page doi:10.1016/s0012-365x(99)00246-0 2000

  46. [46]

    H. Kuai, F. Alajaji, and G. Takahara, Tight error bounds for nonuniform signaling over AWGN channels,IEEE Trans. Inform. Theory46 (2000), 2712–2718. [doi:10.1109/18.887886]. 6

    work page doi:10.1109/18.887886 2000

  47. [47]

    S. M. Kwerel, Bounds on the probability of the union and intersection ofmevents,Advances in Applied Probability7 (1975), 431–448. [doi:10.2307/1426084]. 6

    work page doi:10.2307/1426084 1975

  48. [48]

    Lee,Bonferroni-Type Inequalities, ProQuest LLC, Ann Arbor, MI, 1991

    M.-Y. Lee,Bonferroni-Type Inequalities, ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.), Temple University. 6

    1991

  49. [49]

    Linial and N

    N. Linial and N. Nisan, Approximate inclusion-exclusion,Combinatorica10 (1990), 349–365. [doi:10.1007/BF02128670]. 6

    work page doi:10.1007/bf02128670 1990

  50. [50]

    Luby and B

    M. Luby and B. Veliˇ ckovi´ c, On Deterministic Approximation of DNF,Algorithmica16 (1996), 415–433. [doi:10.1007/s004539900054]. 6

    work page doi:10.1007/s004539900054 1996

  51. [51]

    Mannila, H

    H. Mannila, H. Toivonen, and A. I. Verkamo, Efficient algorithms for discovering association rules, inKnowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical Report WS-94-03(U. M. Fayyad and R. Uthurusamy, Eds.). AAAI Press, 1994, pp. 181–192. 6 17

    1994

  52. [52]

    A. A. Melkman and S. E. Shimony, A note on approximate inclusion-exclusion,Discrete Appl. Math.73 (1997), 23–26. [doi:10.1016/S0166-218X(96)00048-0]. 6

    work page doi:10.1016/s0166-218x(96)00048-0 1997

  53. [53]

    R. A. Moser and G. Tardos, A constructive proof of the general Lov´ asz local lemma,J. ACM 57 (2010), Art. 11, 15. [doi:10.1145/1667053.1667060]. 6

    work page doi:10.1145/1667053.1667060 2010

  54. [54]

    N. J. Nilsson, Probabilistic logic,Artificial Intelligence28 (1986), 71–87. [doi:10.1016/0004- 3702(86)90031-7]. 6

    work page doi:10.1016/0004- 1986

  55. [55]

    Pitowsky, Correlation polytopes: their geometry and complexity,Math

    I. Pitowsky, Correlation polytopes: their geometry and complexity,Math. Programming50 (1991), 395–414. [doi:10.1007/BF01594946]. 3, 4, 5

    work page doi:10.1007/bf01594946 1991

  56. [56]

    Platz, A sharp upper probability bound for the occurrence of at leastmout ofnevents,J

    O. Platz, A sharp upper probability bound for the occurrence of at leastmout ofnevents,J. Appl. Probab.22 (1985), 978–981. [doi:10.1017/s0021900200108241]. 6

    work page doi:10.1017/s0021900200108241 1985

  57. [57]

    Pr´ ekopa, Boole-Bonferroni inequalities and linear programming,Operations Research36 (1988), 145–162

    A. Pr´ ekopa, Boole-Bonferroni inequalities and linear programming,Operations Research36 (1988), 145–162. [doi:10.1287/opre.36.1.145]. 6

    work page doi:10.1287/opre.36.1.145 1988

  58. [58]

    Pr´ ekopa, Inequalities on expectations based on the knowledge of multivariate moments, inStochastic inequalities (Seattle, WA, 1991), Inst

    A. Pr´ ekopa, Inequalities on expectations based on the knowledge of multivariate moments, inStochastic inequalities (Seattle, WA, 1991), Inst. Math. Statist., Hayward, CA, 1992, pp. 309–331. [doi:10.1214/lnms/1215461959]. 6

    work page doi:10.1214/lnms/1215461959 1991

  59. [59]

    Pr´ ekopa and L

    A. Pr´ ekopa and L. Gao, Bounding the probability of the union of events by aggrega- tion and disaggregation in linear programs,Discrete Appl. Math.145 (2005), 444–454. [doi:10.1016/j.dam.2004.03.003]. 6

    work page doi:10.1016/j.dam.2004.03.003 2005

  60. [60]

    Razborov, A simple proof of Bazzi’s theorem,ACM Trans

    A. Razborov, A simple proof of Bazzi’s theorem,ACM Trans. Comput. Theory1 (2009). [doi:10.1145/1490270.1490273]. 6

    work page doi:10.1145/1490270.1490273 2009

  61. [61]

    H. J. Ryser,Combinatorial Mathematics, Mathematical Association of America, ; distributed by John Wiley and Sons, Inc., New York, 1963. 6

    1963

  62. [62]

    Y. S. Sathe, M. Pradhan, and S. P. Shah, Inequalities for the probability of the occur- rence of at leastmout ofnevents,Journal of Applied Probability17 (1980), 1127–1132. [doi:10.1017/s002190020009745x]. 6

    work page doi:10.1017/s002190020009745x 1980

  63. [63]

    E. R. Scheinerman and D. H. Ullman,Fractional Graph Theory, John Wiley & Sons, Inc., New York, 1997. A rational approach to the theory of graphs, With a foreword by Claude Berge, A Wiley-Interscience Publication. 5, 10

    1997

  64. [64]

    Schrijver,Combinatorial Optimization

    A. Schrijver,Combinatorial Optimization. Polyhedra and Efficiency. Vol. A, Springer-Verlag, Berlin, 2003. Paths, flows, matchings, Chapters 1–38. 5

    2003

  65. [65]

    Schrijver,Combinatorial Optimization

    A. Schrijver,Combinatorial Optimization. Polyhedra and Efficiency. Vol. B, Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets, Chapters 39–69. 5

    2003

  66. [66]

    Schrijver,Combinatorial Optimization

    A. Schrijver,Combinatorial Optimization. Polyhedra and Efficiency. Vol. C, Springer-Verlag, Berlin, 2003. Disjoint paths, hypergraphs, Chapters 70–83. 5

    2003

  67. [67]

    A. A. Sherstov, Approximate inclusion-exclusion for arbitrary symmetric functions,Comput. Complexity18 (2009), 219–247. [doi:10.1007/s00037-009-0274-4]. 6 18

    work page doi:10.1007/s00037-009-0274-4 2009

  68. [68]

    Sibuya, Sharp Bonferroni-type inequalities in explicit forms, inProbability Theory and Applications, Kluwer Acad

    M. Sibuya, Sharp Bonferroni-type inequalities in explicit forms, inProbability Theory and Applications, Kluwer Acad. Publ., Dordrecht, 1992, pp. 165–194. 6

    1992

  69. [69]

    T. H. Spencer, Generalized Bonferroni inequalities,J. Appl. Probab.31 (1994), 409–417. [doi:10.2307/3215034]. 6

    work page doi:10.2307/3215034 1994

  70. [70]

    R. P. Stanley,Enumerative Combinatorics. Volume 1, second ed., Cambridge University Press, Cambridge, 2012. 6

    2012

  71. [71]

    M. J. Wainwright and M. I. Jordan, Graphical models, exponential families, and variational inference,Found. Trends Mach. Learn.1 (2008), 1–305. [doi:10.1561/2200000001]. 4, 7

    work page doi:10.1561/2200000001 2008

  72. [72]

    K. J. Worsley, An improved Bonferroni inequality and applications,Biometrika69 (1982), 297–302. [doi:10.1093/biomet/69.2.297]. 6

    work page doi:10.1093/biomet/69.2.297 1982

  73. [73]

    J. Yang, F. Alajaji, and G. Takahara, Lower bounds on the probability of a finite union of events,SIAM J. Discrete Math.30 (2016), 1437–1452. [doi:10.1137/15M100866X]. 6

    work page doi:10.1137/15m100866x 2016

  74. [74]

    G. M. Ziegler, Lectures on 0/1-polytopes, inPolytopes—combinatorics and computation (Ober- wolfach, 1997), Birkh¨ auser, Basel, 2000, pp. 1–41. 5 19

    1997