Bachelor's thesis
Awards: Dean's Award for an Outstanding Final Thesis

Extremal problems with uniform density constraints

Filip Kučerák
Abstract

Jedným z klasických problémov extremálnej kombinatoriky je určiť maximálny počet hrán grafu s n vrcholmi, ktorý neobsahuje zakázaný podgraf F. Napriek mnohým výsledkom v štandardnom režime grafov je naše chápanie problémov týkajúcich sa hypergrafov veľmi obmedzené. Jeden zo známych problémov, na ktorý nemáme odpoveď aj po päťdesiatich rokoch, je Turánov problém štvorstenu z roku 1961. V tomto probléme …more

Abstract

A classical problem in extremal combinatorics is to determine the maximum number of edges a graph on n vertices can have while not containing a forbidden subgraph F. Despite many results in the standard setting of graphs, very little is known about problems concerning hypergraphs. A canonical example of our limited understanding is the famously open problem of Turán from 1961. The problem asks to determine …more

Keywords
extremal combinatorics forbidden subgraphs hypergraphs Turán density uniform density extremálna kombinatorika zakázané podgrafy hypergrafy Turánovské hustoty uniformná hustota
Thesis description
The student will get familiar with the state of the art in the area of uniform Turán densities, which are density threshold for the appearance of a certain substructure with an additional requirement on the uniformity of the density distribution. In the thesis, the student will survey the state of the art in regard to 3-uniform hypergraphs and provide new lower bounds on the uniform Turán density of 5-vertex 3-uniform hypergraphs using the coloring scheme technique, which will be also surveyed in the thesis. An optional (very ambitious) part is to prove exact bounds on the uniform Turán density of specific hypergraphs.
Administrative information
The thesis has been checked:
20/12/2023 09:23, prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Full text of thesis
351,6 KB / file PDF
Language used
English English
Defence date
12/2/2024
The thesis was defended successfully

Supervisor

prof. RNDr. Daniel Kráľ, Ph.D., DSc.
KTP FI MU

Reader

RNDr. Vít Musil, Ph.D., UČO 246021
KTP FI MU
Cite this text
Masaryk University Faculty of Informatics
Programme
Plan
Informatics

Theses on a related topic

List of theses with an identical keyword.

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.