When: Sunday, October 20, 10am
Where: Schreiber 309
Speaker: Raphy Yuster, University of Haifa
Title: Forcing degree repetition
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
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.