Universit� de Grenoble
April 03, 2008, 14:15, Room GC B3 424 (click here for the map)
We consider the problem of minimizing the size of a family of sets G such that every subset of 1,...,n can be written as a disjoint union of at most k members of G, where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the minimum of G so that every subset of 1,...,n is the union of two sets in G has been asked by Erdos and studied recently by Furedi and Katona. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n,k) for which n <= 3k holds, and some individual values of n and k.
Apr�s des �tudes d'Informatique Th�orique � l'Ecole Normale Sup�rieure de Lyon, Benjamin L�v�que a obtenu son dipl�me de doctorat de Math�matiques et Informatique � l'Universit� de Grenoble en 2007. Depuis janvier 2008, il est en post-doctorat � l'Ecole Polytechnique F�d�rale de Lausanne. Ses recherches portent sur les math�matiques discr�tes : optimisation combinatoire, th�orie des graphes, algorithmique, ...