Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"regularity lemma"”.
-
Regularity and removal lemmas and their applications
In this thesis, we analyze the regularity method pioneered by Szemerédi, and also discuss one of its prevalent applications, the removal lemma. First, we prove a new lower bound on the number of parts required in a version of Szemerédi's regularity lemma, determining the order of the tower height …
-
Utilization of Partitions in Graph Structures
… problems and conjectures which require the Regularity lemma require unique methods to improve the bounds on known results. In this work the upper bounds for Gallai-Ramsey using $k$ colors is lowered to at most $k(n-1) +3n$ for even cycles and $(2^{k+3}-3)n \log n$ for odd cycles. Also, with …
-
Precise Partitions Of Large Graphs
<p>First by using an easy application of the Regularity Lemma, we extend some known results about cycles of many lengths to include a specified edge on the cycles. The results in this chapter will help us in rest of this thesis. In 2000, Enomoto and Ota posed a conjecture on the existence of path …
-
Embedding Problems for Graphs and Hypergraphs
… and one for hypergraphs. I will also discuss the regularity lemma for graphs and hypergraphs, an important tool which underpins these and many similar embedding results. Finally, I will also discuss graph and hypergraph Ramsey numbers, since two of the embedding results have important applications …
-
Semi-algebraic graphs and hypergraphs in incidence geometry
… theory such as Ramsey's theorem and Szemerédi's regularity lemma can be significantly improved in the semi-algebraic setting. In this dissertation, we discuss three problems in incidence geometry where the bounds for semi-algebraic (hyper)graphs are generally better than the ones for arbitrary …
-
Sparse regularity and relative Szemerédi theorems
… the sparse setting. First, we consider Szemerédi regularity lemma, a fundamental tool in extremal combinatorics. The regularity method, in its original form, is effective only for dense graphs. It has been a long standing problem to extend the regularity method to sparse graphs. We solve this …
-
Arithmetic regularity lemmas and applications
… investigates various aspects of arithmetic regularity lemmas in the context of vector spaces over finite fields of prime characteristic. Chapter 1 obtains a generalisation of the induced arithmetic removal lemma of Bhattacharyya, Fischer, and Lovett [6] for translation-invariant arithmetic …
-
Formalising Combinatorial Structures and Proof Techniques in Isabelle/HOL
… combinatorial theorems, namely Szemerédi's regularity lemma, Roth's theorem on arithmetic progressions, and the Balog-Szemerédi-Gowers theorem. Through this work, I aim to present a new approach to mathematical formalisation which focuses on developing general, modular formal proof …
-
Three applications of the regularity method in combinatorics
Szemerédi’s regularity lemma is one of the central tools in extremal graph theory and additive combinatorics. We present three versions of this lemma tailored for three applications. The first application considered is the graph removal lemma, which states that for any graph 𝐻 on 𝑘 vertices and all …
-
Extremal problems on special graph colorings
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms