Structures and algorithms in highly symmetric graphs
Project goals
Highly symmetric graphs appear naturally in many different problems in computer science and discrete mathematics, for instance in coding theory, extremal combinatorics or in the study of Boolean functions. The algorithmic problem of generating all objects of a particular combinatorial class - such as bitstrings, permutations, partitions or trees - is another source of a multitude of highly symmetric graphs. In this project, we will investigate fundamental graph structures such as Hamilton cycles, matchings, and colorings in several families of highly symmetric graphs, with an emphasis on algorithmic applications. The core of the proposal are several far-ranging generalizations of the well-known middle levels conjecture, the Ruskey-Savage problem on matching extendability, and Gray code algorithms for different combinatorial objects.
Keywords
hypercubeKneser graphHamilton cyclematchingGray codemiddle levels conjectureposetdiscrete geometry
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
19-08554S
Alternative language
Project name in Czech
Struktury a algoritmy ve velmi symetrických grafech
Annotation in Czech
Velmi symetrické grafy se přirozeně vyskytují v mnoha různých problémech informatiky a diskrétní matematiky, například v teorii kódování, extremální kombinatorice nebo ve studiu Booleovských funkcí. Dalším zdrojem plejády velmi symetrických grafů jsou algoritmické problémy generování všech objektů z daných kombinatorických tříd jakou jsou bitové řetězce, permutace, rozklady či stromy. V tomto projektu budeme zkoumat fundamentální grafové struktury jako jsou Hamiltonovské cykly, párování a barvení v různých třídách velmi symetrických grafů s důrazem na algoritmické aplikace. Jádrem návrhu je několik širokých zobecnění velmi známé hypotézy prostředních vrstev, problém Ruskeyho a Savageové o rozšiřitelnosti párováních a algoritmy pro Grayovy kódy různých kombinatorických objektů.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The financial aspects of the project are in line with the plan. The project fulfilled the original aims and significantly exceeded the number of planned publications. These were often published at essential venues. Therefore, the project reached very good results and should be evaluated accordingly.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Jun 30, 2022
Project status
U - Finished project
Latest support payment
Apr 1, 2022
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP23-GA0-GA-U
Data delivery date
Jun 26, 2023
Finance
Total approved costs
6,482 thou. CZK
Public financial support
6,215 thou. CZK
Other public sources
267 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
6 482 CZK thou.
Public support
6 215 CZK thou.
95%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2019 - 30. 06. 2022