Networks

NWO TOP Grant for Viresh Patel

On 2 November 2016, Dr. Viresh Patel was awarded a TOP Grant by the 'Nederlandse Organisatie voor Wetenschappelijk Onderzoek' (NWO). This Grants was awarded in the TOP Grants Science round 2016, compartment 2.

 

Patel received the grant for his project 'Hamilton cycles in sparse graphs'. Patel, Viresh

 

Abstract

One of the main goals of extremal combinatorics is to understand sharp conditions under which a combinatorial structure contains some substructure of interest. Finding such conditions for spanning substructures in graphs is a very active area of research and one of the most fundamental such substructures is the Hamilton cycle, that is a cycle that passes through every vertex of a graph.

There has been great recent success in solving long-standing problems asking whether dense (directed) graphs with certain conditions contain one or more Hamilton cycles. The Szemerédi Regularity Lemma as well as the recent robust expansion technique have been instrumental in this regard. The goal of this project is to attack long-standing open problems about Hamilton cycles in sparse graphs partly by extending the ideas of robust extension. The problems involve the long-standing conjectures of Chvátal on toughness and Hamiltonicity, and Lovász’s conjecture on Hamiltonicity of connected Cayley graphs. In addition we consider the problem of Hamiltonian resilience: given a graph class that is Hamiltonian, how likely is it to remain Hamiltonian under random edge deletion. The final theme is to investigate applications of methods from extremal graph theory to the algorithmic Hamilton cycle problem.

 

For more information about the NWO Grants visit the NWO website