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


Jianguo Qian, Xiamen University


2017.12.12 16:00-17:00


Middle Lecture Room, Math Building


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.