All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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