Cube edge graph and similar graphs as forbidden structures

Thumbnail Image

Files

master_Zhukov_Matvei_2025.pdf (296.5 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-07-30

Department

Major/Subject

Mathematics

Mcode

Degree programme

Master's Programme in Mathematics and Operations Research

Language

en

Pages

33

Series

Abstract

In extremal graph theory, degenerate (bipartite) extremal graph problems occupy a special place due to Erd{\H{o}}s--Simonovits theorem. One of the smallest graphs for which the asymptotic size of the largest graph avoiding it is unknown is a cube edge graph $Q_8$. Its symmetries and its membership in different classes, such as cycles with all diagonals and prism graphs allows to apply different methods to estimate its extremal numbers. In this thesis a review of known classical and modern methods in degenerate extremal graph theory is given with a focus on the graph $Q_8$ and similar graphs such as hypercube edge graphs and prism graphs. Applicabilities of these approaches are explored and their limitations are analysed.

Description

Supervisor

Freij, Ragnar

Thesis advisor

Šapokaitė, Patricija

Keywords

Turan numbers, extremal graph theory, forbidden subgraph problem, combinatorics, extremal combinatorics, sidorenko conjecture

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202508196304

Collections

[dipl] Perustieteiden korkeakoulu / SCI