Název:
Extremální kombinatorika matic, posloupností a množin permutací
Překlad názvu:
Extremal combinatorics of matrices, sequences and sets of permutations
Autoři:
Cibulka, Josef ; Valtr, Pavel (vedoucí práce) ; Füredi, Zoltán (oponent) ; Jelínek, Vít (oponent) Typ dokumentu: Disertační práce
Rok:
2013
Jazyk:
eng
Abstrakt: [eng][cze] 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 k2 n/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...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 k2 n/2 jedničkami prostou jedné konkrétní permutační matice velikosti k ×...
Klíčová slova:
extremální teorie; množina permutací; zakázaná podstruktura; {0,1}-matice; extremal theory; forbidden substructure; set of permutations; {0,1}-matrix