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 16 of 16 for “"Additive combinatorics"”.
-
Entropy in Data Compression, Additive Combinatorics and Probability
This thesis has four parts: In the first part, the problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the …
-
Results in Extremal Graph Theory, Ramsey Theory and Additive Combinatorics
… contains results from various areas of Combinatorics. In Chapter 2, we consider a central problem in Extremal Graph Theory. The extremal number (or Turán number) ex(n,H) of a graph H is the maximum number of edges in an H-free graph on n vertices. It is a major area of research to better …
-
Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics
… part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in $\mathbb{Z}_N$ (the integers modulo $N$). For all $\epsilon>0$ and $k\in\mathbb{N}$, we construct a subset $A\subset\mathbb{Z}_N$ for some $N$, such that $|A^2+kA|\leq\epsilon …
-
Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science
… one hundred years as a tool to study certain additive patterns. For example, Vinogradov used Fourier-analytic techniques (known in this context as the Hardy-Littlewood circle method) to show that every sufficiently-large odd integer can be written as the sum of three primes, while van der …
-
Random and exact structures in combinatorics
… to notions of randomness and structure in combinatorics and probability. One central notion, the pseudorandomness-structure dichotomy, has played a key role in additive combinatorics and extremal graph theory. More generally, however, such notions come into play in the study of …
-
Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs
… parity edge-colorings, which have connections to additive combinatorics and the minimum dimension of a hypercube in which a tree embeds. In Chapter 6, we prove results on the chromatic number of circle graphs with clique number at most 3. The tournament analogue of an independent set is an acyclic …
-
Algorithms for Subset Sum using linear sketching
… (where m = + [infinity symbol]) with ties to additive combinatorics and cryptography. The non-modular case was long known to be NP-complete but to admit pseudo-polynomial time algorithms and, recently, algorithms running in near-linear pseudo-polynomial time were developed [9, 211. For the …
-
Testability of linear-invariant properties
… computational learning theory, and extremal combinatorics. In the history of the area, a particularly important role has been played by linearinvariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of …
-
Enumerating combinatorial objects with limited sub-configurations
Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several …
-
Three applications of the regularity method in combinatorics
… 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 𝜖 > 0, there is some 𝛿 > 0 such …
-
The sum-product problem
The sum-product problem of Erdos and Szemeredi asserts that any subset of the integers has many products or many sums. We explore quantitative aspects of the problem over both the real numbers and finite fields of prime order.
-
Arithmetic regularity lemmas and applications
This thesis 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 …
-
On equivalence of additive-combinatorial inequalities for Shannon entropy and differential entropy
… In this thesis, we are concerned with the additive-combinatorial entropy inequalities which are motivated by their combinatorial counterparts: cardinality inequalities for subsets of abelian groups. As opposed to the existing approaches in the literature in the study of the discrete and …
-
Additive stucture, rich lines, and exponential set-expansion
… the major directions of research in arithmetic combinatorics and their connections to other fields. We will then discuss three new results. The first result will generalize a structural theorem from Balog and Szemerédi. The second result will establish a new tool in incidence geometry, which …
-
Combinatorial Problems with Geometric Flavour
… respectively. One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ with small $\textit{doubling constant}$ $|A+A|\cdot|A|^{-1}$. Sets $A$ in $\mathbb{R}^k$ have doubling constant at least $2^k$; this is no longer true for …
-
Topics in arithmetic combinatorics
… lead to improvements in a number of existing additive results which we indicate, but for us the main purpose is in application to the analytic problems mentioned above. The second part of the thesis discusses a natural version of Littlewood's problem for finite abelian groups. Here the …