Combinatorial and Graph Theoretical results initiated by application areas

19^th May 2015, 13:00 Ashton Lecture Theater
Prof. Shmuel Zaks
Department of Computer Science
Technion
Israel

Abstract

In this self-contained talk I will describe few results, in the area of Combinatorics and Graph Theory, that were initiated by problems from several application areas. These results are: (1) the use of the Cycle Lemma in deriving statistics about several classes of trees (this includes, as a start, a very simple proof for the Catalan number of binary trees), (2) a new characterization of tree medians , (3) a result about the volume of discrete spheres, (4) a combinatorial problem that resulted in a paper with Paul Erdős, (5) a geometric characterization of an extension of interval graphs, and (6) results concerning approximation algorithms for a problem initiated in Optical Networks.