Combinatorics Seminar

When: Sunday, October 20, 10am Where: Schreiber 309 Speaker: Raphy Yuster, University of Haifa Title: Forcing degree repetition

Abstract:

Every graph with at least two vertices has two vertices with the same degree.

For a given positive integer k, how many vertices must we delete from a graph in order to have k vertices with the same degree? The exact value needed for k=3 is still open.

We prove that there exists an integer C=C(k) such that every graph with n vertices has an induced subgraph with at least n-C vertices whose degree sequence has k repeated values (if n-C < k, then the subgraph may have less than k vertices and is thus required to be regular).

A similar result holds for weighted graphs with bounded integer weights.

A nontrivial lower bound for C(k) is also given, but the gap between the upper bound and the lower bound remains huge.

One of our tools is a multidimensional zero-sum theorem for integer sequences with bounded sum.

Joint work with Y. Caro.