MIDEHA · Minimum degree conditions for tight Hamilton cycles and spanning spheres
„Хоризонт 2020“ — Действия „Мария Склодовска-Кюри“
- Период
- 2022-09-01 → 2024-08-31
- Финансиране от ЕС
- 174 806 €
- Участници
- 1
- Схема
- MSCA-IF
Линиите свързват координатора с партньорите.
Накратко на български
Хиперграфите и техните специални структури, като „стегнати“ Хамилтонови цикли и обхващащи сфери, се анализират чрез минимални условия за степен на върховете. Тези математически модели помагат за оптимизиране на бази данни, компютърна графика и проектиране на електронни схеми.
Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.
Резултати накратко
Minimum degree conditions for tight Hamilton cycles and spanning spheres
The search for Hamilton cycles in graphs and hypergraphs has received much attention in combinatorial research over the past decades. Hamilton cycles in graphs play a fundamental role in many real world problems such as meshes in computer graphics, database theory, circuit design constructions and the Traveling Sales Man problem. Since the problem of finding a Hamilton cycle is computational intractable, the `extremal’ approach has been to identify optimal minimum degree conditions. A classic example for such a result in the graph setting is Dirac’s theorem. For hypergraphs, the concept of cycles has been generalised in several ways. A tight cycle in a k-uniform hypergraph consists of rigidly interlocked edges following a cyclic ordering: every k consecutive vertices form an edge. Tight Hamilton cycles have been studied extensively in the last twenty years and many of the developed techniques have found application in seemingly more complex problems. A second generalization of cycles is topological and emphasises the ‘higher dimensional’ nature of hypergraphs. Consider a cycle in a graph and observe that the simplicial complex induced by the cycle’s edges is homeomorphic to the 1-dimensional sphere. By analogy, we define a sphere in a k-graph as a set of edges whose induced simplicial complex is homeomorphic to a (k-1)-dimensional sphere and it is spanning if it contains all vertices. Spheres in hypergraphs were already considered by Brown, Erdős and Sós but the systematic investigation of these structures, and more general the study of ‘higher dimensional’ combinatorics, has only taken off quite recently. The goal of this research project is to investigate the existence of tight Hamilton cycles and spanning spheres in hypergraphs under minimum degree conditions. To this end, a new framework for embedding large structures into hypergraphs shall be developed and tested on a series of open problems in the area.
Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз
Цел на проекта
One of the most exciting developments in the second half of the last century in combinatorial research has been the search for Hamilton cycles in graphs and hypergraphs. Since the decision problem, whether a given graph contains a Hamilton cycle, is computationally intractable, no `simple' characterization for their existence is known. The main approach to finding Hamilton cycles has thus focused on natural sufficient conditions. A classic example for this is Dirac's theorem, which provides optimal minimum degree conditions for the existence of a Hamilton cycle in graphs.The aim of this project is to resolve several problems regarding hypergraph analogues of Dirac's theorem. The proposed research considers two natural generalization of cycles: (i) Tight cycles, which have been extensively researched in the past two decades, and (ii) Spheres, a topological generalization of cycles, which was suggested by Brown, Erdős and Sós in the Seventies and has recently resurfaced in extremal graph theory. To determine optimal minimum degree conditions for spanning tight cycles and spheres, the experienced researcher plans to develop new techniques based on hypergraph regularity and combinatorial optimization, which will likely find application beyond the proposed research.
Оригинален текст от CORDIS (на английски).
Участници
- UNIVERSITY OF HAMBURG · HamburgКоординаторГермания
Връзки
Данни: CORDIS, © Европейски съюз