velikost textu

Extremal combinatorics of matrices, sequences and sets of permutations

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Extremal combinatorics of matrices, sequences and sets of permutations
Název v češtině:
Extremální kombinatorika matic, posloupností a množin permutací
Typ:
Disertační práce
Autor:
RNDr. Josef Cibulka, Ph.D.
Školitel:
doc. RNDr. Pavel Valtr, Dr.
Oponenti:
Prof. Zoltán Füredi
RNDr. Vít Jelínek, Ph.D.
Id práce:
44653
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
29. 3. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
extremální teorie, zakázaná podstruktura, množina permutací, {0,1}-matice
Klíčová slova v angličtině:
extremal theory, forbidden substructure, set of permutations, {0,1}-matrix
Abstrakt:
Název práce: Extremální kombinatorika matic, posloupností a množin permutací Autor: Josef Cibulka Katedra: Katedra aplikované matematiky Vedoucí disertační práce: Doc. RNDr. Pavel Valtr, Dr., Katedra aplikované ma- tematiky Abstrakt: V této práci se zabýváme oblastmi extremální teorie {0, 1}-matic, posloupností a množin permutací, které mají četná využití v oblasti kombina- torické a výpočetní geometrie. VC-dimenze množiny n-prvkových permutací P je největší celé číslo k takové, že množina zúžení permutací z P na některou k-tici pozic je množina všech k-prvkových permutací. Projdeme všemi třemi zmíněnými oblastmi extremální kombinatoriky, abychom dokázali horní a dolní meze, rostoucí kvaziexponenciálně v n, na maximální možnou velikost množiny n- permutací s VC-dimenzí shora omezenou konstantou. Tento výsledek využívá ve svém článku Jan Kynčl k výraznému snížení horního odhadu na počet tříd slabého izomorfismu úplného topologického grafu na n vrcholech. Dále pro některé, ze- jména permutační, matice M dokážeme nové meze na počet jedniček v M -prosté {0, 1}-matici velikosti n × n. Například pro každé k zkonstruujeme matici s k2n/2 jedničkami prostou jedné konkrétní permutační matice velikosti k × k. Také dokážeme téměř těsné meze na maximální počet jedniček v matici prosté pevně zvolené vrstvené permutační matice. Klíčová slova: extremální teorie, zakázaná podstruktura, množina permutací, {0, 1}-matice
Abstract v angličtině:
Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M , we give new bounds on the number of 1-entries an n × n M -avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered permutation matrix. Keywords: extremal theory, forbidden substructure, set of permutations, {0, 1}- matrix
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Josef Cibulka, Ph.D. 1.49 MB
Stáhnout Abstrakt v českém jazyce RNDr. Josef Cibulka, Ph.D. 54 kB
Stáhnout Abstrakt anglicky RNDr. Josef Cibulka, Ph.D. 55 kB
Stáhnout Posudek vedoucího doc. RNDr. Pavel Valtr, Dr. 18 kB
Stáhnout Posudek oponenta Prof. Zoltán Füredi 106 kB
Stáhnout Posudek oponenta RNDr. Vít Jelínek, Ph.D. 63 kB
Stáhnout Záznam o průběhu obhajoby 84 kB