We give two combinatorial proofs to a formula by Alkam, Osba and Tóth on the number of regular elements in Z_n based on the inclusion-exclusion principle and the bijection principle.

Keywords: regular element, unitary divisor, modular multiplication, totient, inclusion-exclusion

The orbital chromatic polynomial introduced by Cameron and Kayibi counts the number of proper λ-colorings of a graph modulo a group of symmetries. In this paper, we establish expansions for the orbital chromatic polynomial of the n-cycle for the group of rotations and its full automorphism group. Besides, we obtain a new proof of Fermat’s Little Theorem.

Keywords: chromatic polynomial, cycle, graph, automorphism group, dihedral group, totient function, cycle index, Fermat’s Little Theorem

We establish closed-form expansions for the universal edge elimination polynomial of paths and cycles and their generating functions. This includes closed-form expansions for the covered components polynomial, the bivariate chromatic polynomial, and the bivariate matching polynomial.

Keywords: graph polynomial, chromatic polynomial, matching polynomial, covered components polynomial, edge elimination, generating function, path, cycle, closed-form

We establish a broad generalization of Whitney's broken circuit theorem on the chromatic polynomial of a graph to sums of type ∑_A⊆S f(A) where S is a finite set and f is a mapping from the power set of S into an abelian group. We give applications to the domination polynomial and the subgraph component polynomial of a graph, the chromatic polynomial of a hypergraph, the characteristic polynomial and Crapo's beta invariant of a matroid, and the principle of inclusion-exclusion. Thus, we discover several known and new results in a concise and unified way. As further applications of our main result, we derive a new generalization of the maximums-minimums identity and of a theorem due to Blass and Sagan on the Möbius function of a finite lattice, which generalizes Rota's crosscut theorem. For the classical Möbius function, both Euler's totient function and its Dirichlet inverse, and the reciprocal of the Riemann zeta function we obtain new expansions involving the greatest common divisor resp. least common multiple. We finally establish an even broader generalization of Whitney's broken circuit theorem in the context of convex geometries (antimatroids).

Keywords: graph polynomial, domination polynomial, beta invariant, broken circuit, Möbius function, lattice, max-min identity, totient, Dirichlet inverse, Riemann zeta function, closure system, convex geometry

We establish new Bonferroni-type lower bounds for the probability of a union of finitely many events where the selection of intersections in the estimates is determined by the clique complex of a chordal graph.

Keywords: Bonferroni inequalities, probability, union, chordal graph, clique complex

We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard.

Keywords: graph, domination, reliability, polynomial, cograph, hypergraph, decomposition, inclusion-exclusion, broken circuit, NP-hard

We present a new proof of Whitney's broken circuit theorem based on induction on the number of edges and the deletion-contraction formula.

Keywords: graph, chromatic polynomial, deletion-contraction, broken circuit, inductive proof

We present a unified approach to an important subclass of Bonferroni-type inequalities by considering the so-called binomially bounded functions. Our main result associates with each binomially bounded function a Bonferroni-type inequality. By appropriately choosing this function, several well-known and new results are deduced in a concise and unified way.

Keywords: Bonferroni inequalities, graph, hypergraph, binomially bounded function, probability bounds

We show how the X Resize, Rotate and Reflect Extension of the X Window System can be used to display a LaTeX beamer presentation on one or two beamers while simultaneously displaying the output of both beamers on the lecturer's display. If only one beamer is used, the lecturer's display might show both the beamer output and hidden notes.

Keywords: LaTeX, Beamer, dual-screen, X Window System, xrandr

We introduce the concept of a binomially bounded function and associate with each such function an improved Bonferroni-type inequality

Keywords: Bonferroni inequalities, graph, hypergraph, binomially bounded function, probability bounds

In this paper, we generalize the classical Bonferroni inequalities and their improvements by Galambos to sums of type sum_{Isubseteq U} (-1)^{vert Ivert} f(I) where U is a finite set and f:2^UrightarrowmathbbR. The result is applied to the Tutte polynomial of a matroid and the chromatic polynomial of a graph.

Keywords: Bonferroni inequalities, graph, matroid, chromatic polynomial, Tutte polynomial, inclusion-exclusion

In this paper, we establish a new analogue of the classical Bonferroni inequalities and their improvements by Galambos for sums of type ∑_π∈P(U) (-1)^|π|-1 (|π|-1)! f(π) where U is a finite set, P(U) is the partition lattice of U and f: P(U)→R is some suitable non-negative function. Applications of this new analogue are given to counting connected k-uniform hypergraphs, network reliability, and cumulants.

Keywords: Bonferroni inequalities, cumulants, partition lattice, probability bounds

We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph. This new polynomial satisfies both an edge decomposition formula and a vertex decomposition formula. We establish two general expressions for this new polynomial: one in terms of the broken circuit complex and one in terms of the lattice of forbidden colorings. We show that the new polynomial may be considered as a specialization of Stanley's chromatic symmetric function. We finally give explicit expressions for the generalized chromatic polynomial of complete graphs, complete bipartite graphs, paths, and cycles, and show that it can be computed in polynomial time for trees and graphs of restricted pathwidth.

Keywords: graph, bivariate chromatic polynomial, lattice of forbidden colourings, broken circuit

This paper establishes a connection between the theory of convex geometries, the principle of inclusion-exclusion, and the topological concept of an abstract tube. In particular, it is shown that convex geometries give rise to improved inclusion-exclusion identities and improved Bonferroni inequalities. In this way, several known results from the literature are rediscovered in a concise and unified way. The results are applied in identifying a new class of hypergraphs for which the reliability covering problem can be solved in polynomial time.

Keywords: graph, hypergraph, system reliability, Bonferroni inequalities, inclusion-exclusion, abstract tube, closure operator, abstract simplicial complex, convex geometry, probability bounds

This introduction to the recent theory of abstract tubes describes the framework for establishing improved inclusion-exclusion identities and Bonferroni inequalities, which are provably at least as sharp as their classical counterparts while involving fewer terms. All necessary definitions from graph theory, lattice theory and topology are provided. The role of closure and kernel operators is emphasized, and examples are provided throughout to demonstrate the applicability of this new theory. Applications are given to system and network reliability, reliability covering problems and chromatic graph theory. Topics also covered include Zeilberger's abstract lace expansion, matroid polynomials and Möbius functions.

Keywords: graph, hypergraph, matroid, probability bounds, system reliability, network reliability, Bonferroni inequalities, inclusion-exclusion, abstract tube, closure operator, kernel operator, semilattice, chromatic polynomial, Tutte polynomial, abstract simplicial complex, Euler characteristic, convex geometry, bivariate chromatic polynomial

We consider improved inclusion-exclusion identities for dependent families of sets, where a family of sets is called dependent if the intersection of some sets is included by the union of the others.

Keywords: inclusion-exclusion, intersection sizes, independence

We present a new and elementary proof of some recent improvements of the classical inclusion-exclusion bounds. The key idea is to use an injective mapping, similar to the bijective mapping in Garsia and Milne's bijective proof of the classical inclusion-exclusion principle.

Keywords: Bonferroni inequalities, inclusion-exclusion, kernel operator, bijective proof

We restate a recent improvement of the inclusion-exclusion principle in terms of valuations on distributive lattices and present a completely new proof of the result. Moreover, we establish set-theoretic identities and logical equivalences of inclusion-exclusion type, which have not been considered before.

Keywords: distributive lattice, valuation, inclusion-exclusion

We establish a Bonferroni-type inequality where the selection of intersections in the estimates is determined by the clique complex of a chordal graph G. It interpolates between Boole's inequality (G empty) and the sieve formula (G complete). By varying G, several inequalities both well-known and new are obtained in a concise and unified way.

Keywords: Bonferroni inequalities, chordal graph, clique complex, probability bounds

In this paper, we show that any convex geometry (dual antimatroid) gives rise to a lace map and deduce some recent variants of the inclusion-exclusion principle from Zeilberger's abstract lace expansion.

Keywords: abstract lace expansion, dual antimatroid, convex geometry, inclusion-exclusion, lace map

Many problems in combinatorics, number theory, probability theory, reliability theory and statistics can be solved by applying a unifying method, which is known as the principle of inclusion-exclusion. The principle of inclusion-exclusion expresses the indicator function of a union of finitely many events as an alternating sum of indicator functions of their intersections. This thesis deals with improved inclusion-exclusion identities and improved Bonferroni inequalities that require the family of events to satisfy some structural restrictions. Examples of such well-structured families arise in problems of statistical inference, combinatorial reliability theory and chromatic graph theory.

Keywords: graph, hypergraph, matroid, probability bounds, system reliability, network reliability, Bonferroni inequalities, inclusion-exclusion, abstract tube, closure operator, kernel operator, semilattice, chromatic polynomial, Tutte polynomial, abstract simplicial complex, Euler characteristic, convex geometry, bivariate chromatic polynomial

We restate and reprove Narushima's principle of inclusion-exclusion on partition lattices in terms of abstract tubes. In this way, some new Bonferroni-like inequalities for partition lattices are obtained.

Keywords: Inclusion-exclusion, partition lattice, order complex

We draw a conclusion from Narushima's inclusion-exclusion variant for semilattices, thus generalizing a well-known result on the Euler function of number theory.

Keywords: inclusion-exclusion, semilattice, Möbius function

We establish a connection between the principle of inclusion-exclusion and the union-closed sets conjecture. In particular, it is shown that every counterexample to the union-closed sets conjecture must satisfy an improved inclusion-exclusion identity.

Keywords: Frankl's conjecture, inclusion-exclusion, semilattice, order complex

We reprove an important case of a recent topological result on improved Bonferroni inequalities due to Naiman and Wynn in a purely combinatorial manner. Our statement and proof involves the combinatorial concept of non-evasiveness instead of the topological concept of contractibility. In contradistinction to the proof by Naiman and Wynn, our proof does not require knowledge of simplicial homology theory.

Keywords: Bonferroni inequalities, abstract simplicial complex, evasiveness, contractibility, probability bounds

We present a new variant of the sieve formula as well as new expansions for the Tutte polynomial and Crapo's beta invariant, where the number of terms is reduced by excluding terms that cancel.

Keywords: graph, matroid, Tutte polynomial, beta invariant

We investigate the number of proper λ-colourings of a hypergraph extending a given proper precolouring. We prove that this number agrees with a polynomial in λ for any sufficiently large λ, and we establish a generalization of Whitney's broken circuit theorem by applying a recent improvement of the inclusion-exclusion principle.

Keywords: graph, hypergraph, chromatic polynomial, precolouring, broken circuit

In this paper an improved sieve formula containing a smaller number of terms for any suitable closure operator on the power set of the index set is established, thus generalizing several well-known results from the literature.

Keywords: inclusion-exclusion, closure operator, Boolean algebra

We regard the terms occuring in the inclusion-exclusion principle as nodes of a rooted tree and identify each set of cancelling terms with a subtree of this tree.

Keywords: inclusion-exclusion, rooted tree, partial order

Let (A_v)_v∈V be a finite family of sets. We establish an improved inclusion-exclusion identity for each closure operator on the power set of V having the unique base property. The result generalizes three improvements of the inclusion-exclusion principle as well as Whitney's broken circuit theorem on the chromatic polynomial of a graph.

Keywords: inclusion-exclusion, convex geometry, closure operator

By applying a recent result of Naiman and Wynn on abstract tubes, we establish a new improvement of the classical Bonferroni inequalities for any finite collection of sets {A_v}_v∈V associated with an additional structure, which is assumed to be given by a union-closed set X of non-empty subsets of V such that _x∈X A_x ⊆_v∉X A_v for any X∈X. The result generalizes several other results from the literature.

Keywords: Bonferroni inequalities, inclusion-exclusion, set system, abstract tube, abstract simplicial complex, Euler characteristic, probability bounds

We establish a general theorem for reducing sums of type ∑_y≥x g(y) where g is a mapping from a partially ordered set into an abelian group. Conclusions concern the Möbius function, the principle of inclusion-exclusion, the Tutte polynomial and Crapo's beta invariant.

Printed version: J. Combin . 6 (1999), 459–468

Keywords: partially ordered set, poset, graph, matroid, Möbius function, chromatic polynomial, Tutte polynomial

In this paper we prove that the partial sums of the chromatic polynomial of a graph define an alternating sequence of upper and lower bounds.

Keywords: graph, chromatic polynomial, Bonferroni inequalities

Recently, Naiman and Wynn introduced the concept of an abstract tube in order to obtain improved inclusion-exclusion identities and inequalities that involve much fewer terms than their classical counterparts. In this paper, we introduce a particular class of abstract tubes which plays an important role with respect to chromatic polynomials and network reliability. The inclusion-exclusion identities and inequalities associated with this class simultaneously generalize several well-known results such as Whitney's broken circuit theorem, Shier's expression for the reliability of a network as an alternating sum over chains in a semilattice and Narushima's inclusion-exclusion identity for posets. Moreover, we show that under some restrictive assumptions a polynomial time inclusion-exclusion algorithm can be devised, which generalizes an important result of Provan and Ball on network reliability.

Keywords: Bonferroni inequalities, inclusion-exclusion, sieve formula, abstract tube, partial order, chain, graph, chromatic polynomial, broken circuit, system reliability, network reliability, probability bounds

We present a new improvement of the classical Bonferroni inequalities and show how this improvement can be utilized in bounding the reliability of a communication network whose nodes are perfectly reliable and whose edges are subject to random and independent failure.

Keywords: Bonferroni inequalities, system reliability, network reliability, bounds

We establish a connection between the theory of convex geometries, the principle of inclusion-exclusion and the theory of abstract tubes. In particular, it is shown that convex geometries give rise to improved inclusion-exclusion identities and via abstract tubes to improved Bonferroni inequalities. Thus, several results from the literature are rediscovered in a concise and unified way. Our general results are applied in identifying a new class of hypergraphs for which the reliability covering problem can be solved in polynomial time.

Keywords: convex geometry, inclusion-exclusion, Bonferroni inequalities, sieve formula, abstract tube, abstract simplicial complex, contractible, partition lattice, system reliability, reliability covering problem, domination theory

In this paper, we establish a new upper bound to the chromatic number of a uniform hypergraph having no cycles of length two or three. The proof is based on a recent lower bound to the chromatic polynomial.

Keywords: hypergraph, chromatic number, upper bound

We present an improvement of the inclusion-exclusion principle in which the number of terms is reduced by predicted cancellation. The improvement generalizes a related result of Narushima as well as a graph-theoretic theorem of Whitney. Applications concern chromatic polynomials of graphs and permanents of 0,1-matrices.

Keywords: inclusion-exclusion, cancellation, chromatic polynomial, broken circuit, permanent

We propose a modification of Karp's inclusion-exclusion algorithm for counting Hamiltonian paths in graphs. Experiments on random graphs suggest that this modification leads to a significant reduction of the average running time when the input graphs are sparse.

Keywords: Hamiltonian paths, counting, inclusion-exclusion, algorithm

Based on a recent improvement of the inclusion-exclusion principle, we present a new approach to network reliability problems. In particular, we give a new proof of a result of Shier, which expresses the reliability of a network as an alternating sum over chains in a semilattice, and a new proof of a result of Provan and Ball, which provides an algorithm for computing network reliability in pseudopolynomial time. Moreover, some results on k-out-of-n systems are established.

Printed version: J . Combin . 5 (1998), 537–544.

Keywords: inclusion-exclusion, system reliability, network reliability, semilattice, k-out-of-n system

We present a new improvement upon the classical Bonferroni inequalities and show how this improvement can be utilized in bounding the reliabilty of a communication network whose nodes are perfectly reliable and whose edges are subject to random and independent failure.

Keywords: Bonferroni inequalities, system reliability, network reliability, bounds

An inductive proof by induction on the number of edges of some recently published Bonferroni-type bounds to the chromatic polynomial of a graph is presented.

Keywords: graph, chromatic polynomial, girth, Bonferroni inequalities, bounds

A theorem on Möbius inversion over power set lattices is established. The main result is a modification of the formula which, when applied to graphs or hypergraphs, is a generalization of Whitney's broken circuits theorem on graph colouring.

Keywords: graph, hypergraph, Möbius inversion, power set lattice, chromatic polynomial, broken circuit

As a generalization of chromatic polynomials, this paper deals with real-valued mappings ψ on the class of graphs satisfying ψ(G₁) = ψ(G₂) for all pairs G₁, G₂ of isomorphic graphs and ψ(G) = ψ(G − e) − ψ(G/e) for all graphs G and all edges e of G, where the definition of G/e is nonstandard. In particular, new inequalities for chromatic polynomials are presented.

Keywords: graph, deletion-contraction invariant, chromatic polynomial, bounds, inductive proof

Keywords: hypergraph, chromatic polynomial, chromatic number

We define the chromatic polynomial of a hypergraph and establish a generalisation of Whitney's broken-circuits-theorem.

Keywords: graph, hypergraph, chromatic polynomial, broken circuit

Keywords: graph, hypergraph, chromatic polynomial, broken circuit, deletion-contraction, bounds

In this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs on n vertices having m edges and girth exceeding g.

Keywords: graph, chromatic polynomial, bounds

Keywords: Assembler, Z80, real-time programming