Logo

Ordering-Free Cancellation in the Principle of Inclusion-Exclusion and its Application to Graph Polynomial

Speaker

Jianguo Qian, Xiamen University

Time

2017.12.12 16:00-17:00

Venue

Middle Lecture Room, Math Building

Abstract

Whitney’s broken circuit theorem gives a graphical example to reduce the number of the terms in the sum of the inclusion-exclusion formula by a predicted cancellation. So far, the known cancellations for inclusion-exclusion formula strongly depend on the prescribed (linear or partial) ordering on the index set. We introduce a new cancellation method, which does not require any ordering on the index set and therefore, may reduce more terms than by the methods known in the literatures. We also discuss its application to graph polynomials.