Problems in Extremal Combinatorics

advisor:	Mgr. Jan Volec, Ph.D.
e-mail:	show e-mail
type:	phd thesis
branch of study:	MINF
key words:	computer assisted proofs, flag algebras, pseudorandomness, regularity method
description:	The main topic of this thesis is to tackle open problems in combinatorics by recently developed tools such as those based on the regularity lemma and the absorption method, the flag algebra method, and the probabilistic method. A particular focus will be given to incorporating computer in establishing rigorous proofs (e.g. using SAT solvers, linear and semidefinite programming). While tackling some of the combinatorial conjectures, it is expected that the known methods will require novel extensions, which forms a secondary theme of this project. The student will also seek for applications of the newly established results to open problems in other related areas of mathematics such as number theory, discrete geometry, and theoretical computer science. Although this PhD topic is closely related to the PhD topic "Modern Methods in Discrete Mathematics" of the same supervisor, it is expected that the respective students will be working on disjoint research tasks. The student working on this research topic is expected to have a strong background in extremal graph theory, and at least a basic background in analysis and programming. The student working on this research topic will be supported by the project Extremal and Probabilistic Combinatorics - GAČR 23-06815M - funded by Czech Science Foundation.
references:	N. Alon, J. Spencer: The Probabilistic Method, 4th Edition, Wiley, 2016. S. Jukna: Extremal Combinatorics, Second Edition, Springer, 2011. L. Lovasz: Large Networks and Graph Limits, American Mathematical Society, 2012. A. Razborov: Flag Algebras, Journal of Symbolic Logic 72(4), 2007, 1239-1282. Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023.
last update:	03.05.2024 11:15:28

administrator for this page: Ľubomíra Dvořáková | last update: 09/12/2011