Thesis topic proposal
Gyula Y. Katona
Hamilton Cycle Problems in Hypergraphs


Institute: Budapest University of Technology and Economics
computer sciences
Doctoral School of Informatics

Thesis supervisor: Gyula Y. Katona
Location of studies (in Hungarian): Department of Computer Science and Information Theory
Abbreviation of location of studies: SZIT

Description of the research topic:

The concept of Hamilton cycles can be generalized to hypergraphs in several ways. One such interesting definition can be found in an article of Katona and Kirstead in 1999:
A Hamilton cycle of an r-uniform hypergraph is an ordering of the vertices of the hypergraph in a cyclic way such that any consecutive r vertices forms an edge of the hypergraph.
The first result for this was a proof of a Dirac-type sufficient condition, which was later improved by Rödl, Rucsinski and Szemerédi. Over the past 18 years, more than 50 articles have been written on the topic. Because problems are usually more difficult than in graphs, in most cases, the results are not sharp or there is still room for improvement. In addition, there are countless questions that are not dealt with in substance.

A few specific tasks question for example:

• Ore-type condition for Hamilton cycles
• How many edges a hypergraph can have if it does not contain a Hamilton cycle?
• Can one partition the edges of a complete hypergraph into a union of Hamilton cycles?

Required language skills: English
Further requirements: 
graph theory knowledge

Number of students who can be accepted: 2

Deadline for application: 2019-06-14

All rights reserved © 2007, Hungarian Doctoral Council. Doctoral Council registration number at commissioner for data protection: 02003/0001. Program version: 2.2358 ( 2017. X. 31. )