Master's thesis

Quasirandomness in combinatorics

Bc. Filip Kučerák
Abstract

Matematický objekt nazývame kvazináhodný, ak jeho správanie pripomína správanie skutočne náhodného objektu rovnakého typu. V tejto diplomovej práci sa snažíme určiť hranicu postačujúcich podmienok pre túto vlastnosť v kombinatorickej triede permutácií. Je známe, že permutácia je kvazináhodná práve vtedy, ak sa hustota všetkých permutácií na štyroch prvkoch nevzďaľuje od očakávanej hodnoty 1/24. Podmnožinám …more

Abstract

An object is said to be quasirandom if it resembles a truly random object from the same structure class. In this thesis, we focus on determining the boundary of sufficient conditions for the property in the combinatorial setting of permutations. It is known that a permutation is quasirandom if and only if the density of all four-element permutations does not significantly deviate from their expected …more

Keywords
permutations permutation limits quasirandomness quasirandom-forcing permutácie permutačné limity kvazináhodnosť vynútenie kvazináhodnosti
Thesis description
Quasirandom combinatorial structures play an important role in computer science as they are specific objects that possess properties that a random object of the same kind would have almost surely. This master's thesis will be focused on the study of quasirandom properties of permutation. The main goal is to improve the existing lower bounds on the number of permutation patterns needed to characterize permutation quasirandomness.
Administrative information
The thesis has been checked:
22/5/2025 07:28, prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Full text of thesis
478,7 KB / file PDF
Attachments (2)
Language used
English English
Defence date
19/6/2025
The thesis was defended successfully

Supervisor

prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Reader

Mgr. Marek Filakovský, Ph.D., UČO 211334
KTP FI MU
Cite this text
Masaryk University Faculty of Informatics
Programme
Plan
Discrete algorithms and models

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.