# Minimum partition of an independence system

*by Dr Sanming Zhou *

*Institution:*The University of Melbourne

*Date: Thu 6th November 2008*

*Time: 1:00 PM*

*Location: Room 213, Richard Berry Bldg, The University of Melbourne*

*Abstract*: An independence system is a set E together with a family J of subsets, called independent, of E such that any subset of an independent set is also independent. In terms of combinatorial topology, an independence system is a simplicial complex. Given a finite independence system (E, J), the Minimum Partition Problem (MPP) seeks a partition of E into the least number of independent sets. This fundamental problem provides a unifying framework for a number of combinatorial optimisation problems, including various conditional colouring problems for graphs. The smallest integer n such that E can be partitioned into n independent sets is called the J-chromatic number of E. We will talk about connections between MPP and a few other well-studied optimisation problems and a sequential colouring algorithm. In particular, by showing that the J-chromatic number is equal to the domination number of a split graph associated with (E, J), we give a few upper bounds on the J-chromatic number of E in terms of some basic invariants of (E, J).

*For More Information:* Mark Fackrell mfackrel@ms.unimelb.edu.au