Mgr. Jan Volec, Ph.D.
Důkaz Goldberg-Seymourovy domněnky s pomocí počítače
| advisor: |
Mgr. Jan Volec, Ph.D. |
| e-mail: |
show e-mail
|
| type: |
|
| branch of study: |
MINF, APIN |
| key words: |
Teorie grafů, hranová barevnost, párování, počítačově asistované důkazy |
| link: |
http://honza.ucw.cz/thesis
|
| description: |
Tématem této práce je jeden z nejznámějších problémů z oblasti hránové barevnosti grafů, kde je cílem pokrýt množinu hran grafu co nejmenším počtem párování. Jinými slovy, chceme všem hranám přiřadit barvy tak, aby každé dvě sousední hrany dostaly různou barvu.
Goldberg-Seymourova domněnka o hranové barevnosti multigrafů říká, že libovolný multigraf jehož každý vrchol má stupeň nejvýše D lze hranově obarvit pomocí max(D+1, w) barev, kde w značí nejmenší přirozené číslo takové, že pro všechny H podgrafy G s lichým počtem vrcholů číslo w shora odhaduje zlomek 2|E(H)|/(|V(H)|-1). Číslo w je zajisté dolním odhadem, a stejně tak je dolním odhadem i číslo D. Přestože Petersenův graf má D=3 i w=3, je známo, že není hranově-3-obarvitelný, a proto je max(D+1,w) nejlepší horní odhad, v jaký lze doufat.
Cílem této práce je nastudovat nedávný důkaz Goldberg-Seymourovy domněnky a případně též navrhnout verifikaci pomocných tvrzení v tomto důkazu pomocí počítače. |
| references: |
A. Bondy, U.S.R. Murty: Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008
G. Chen, G. Jing, W. Zang: Proof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs, https://arxiv.org/abs/1901.10316
https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture |
| last update: |
03.05.2024 11:20:25 |
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 |
Modern Methods in Discrete Mathematics
| advisor: |
Mgr. Jan Volec, Ph.D. |
| e-mail: |
show e-mail
|
| type: |
phd thesis
|
| branch of study: |
MINF |
| key words: |
limits of discrete structures, polynomial method, combinatorial optimization, probabilistic method |
| description: |
The aim of this thesis is to establish new algebraic, probabilistic and analytic methods to tackle open problems in discrete mathematics and theoretical computer science. A particular focus will be given to developing novel tools within the very active research area of limits of discrete structures, and using algebraic techniques (e.g. the polynomial method) and probabilistic tools (e.g. concentration inequalities, the Lovász local lemma).
The newly developed methods will be used to tackle well-known open problems including Turán-type problems, graph and hypergraph decompositons, quasirandomness of discrete structures, and questions in Ramsey Theory.
Although this PhD topic is closely related to the PhD topic "Problems in Extremal Combinatorics" 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 analysis and algebra, and at least a basic background in discrete mathematics.
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.
L. Guth: Polynomial Methods in Combinatorics, American Mathematical Society, 2016.
L. Lovasz: Large Networks and Graph Limits, American Mathematical Society, 2012.
M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method, Springer, 2002.
Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023. |
| last update: |
03.05.2024 11:15:36 |
V3S Database
The application records results of science and research, and other academic activities. The V3S application serves as a tool for submitting data to the RIV database, exporting data for statistic analyses, and internal evaluation of research.
List of publications in V3S
administrator for this page:
Radek Fučík | last update: 08/07/2011
