Doctor of Philosophy in Mathematics (PhD)
Extremal problems, in general, ask for the optimal size of certain finite objects when some restrictions are imposed. In extremal combinatorics, a major field in combinatorics, one studies how global properties guarantee the existence of local substructures, or equivalently, how avoiding local substructures poses a constraint on global quantities. In this thesis, we study the following three problems in combinatorics.The first problem is related to the Brown–Erdos–Sos conjecture, which can bereformulated as a problem of finding a dense substructure, namely a large numberof triples, spanned by a given number of elements in a quasigroup. In the special case of finite groups, we show in Chapter 2 that in every dense set of triples, there exists a subset of m elements which spans 4m/3 (1 − o(1)) triples, as m tends to infinity, which is much higher than the conjectured amount m − 3 for a general quasigroup. Later in the chapter, we give an elementary proof that, in finite groups, the maximum number of triples spanned by m elements has order m².The second problem concerns planar polygons in the 3-space. The maximum possible number of polygons from a given number of points is controlled by their intersection properties. Two hexagons in the space are said to intersect badly if their intersection consists of at least one common vertex as well as an interior point. In Chapter 3, we show that the number of hexagons on n points in 3-space without bad intersections is o(n²), under a mild assumption that the hexagons are ‘fat’. The main tool we used is the triangle removal lemma.The last problem in this dissertation is about the sum-product conjecture of Erdos and Szemeredi. The sum-product estimate concerns the larger size of the sumset and productset in terms of the size of the set itself. In Chapter 4 we prove an estimate with exponent 4/3 for the ring of quaternions and a certain family of well-conditioned matrices, using the boundedness of the kissing numbers.
In this thesis, we investigate topics related to the Green-Tao theorem on arithmetic progression in primes in higher dimensions. Our main tool is the pseudorandom measure majorizing primes defined in  concentrated on almost primes. In chapter 2, we combine the sieve technique used in constructing pseudorandom measure (in this case, Goldston-Yildirim sum and almost primes) with the circle method of Birch to study the number of almost prime solutions of diophantine systems (with some rank conditions). Our rank condition is similar to the integer case, due to the heuristics that almost primes are pseudorandom. In chapter 3, we investigate the generalization of Green-Tao’s theorem to higher dimensions in the case of corner configuration. We apply the transference principle of Green-Tao (with hyperplane separation technique of Gowers) in this setting. This problem is also related to the densification trick in . In chapter 4, we extend the result of Chapter 3 to obtain the full multi-dimensional analogue of the Green-Tao’s theorem, using hypergraph regularity method by directly proving a version of hypergraph removal lemma in the weighted hypergraphs. The method is to run an energy increment on a parametric weight systems of measures, rather than on a single measure space, to overcome the presence of intermediate weights. Contrary to ,  where theauthors investigate the problem using a measure supported on primes and infinite linear form conditions, relying on the Gowers Inverse Norms Conjecture.
In this thesis we give results on unit and rational distances, structure results for surfaces containing many points of a cartesian product and a survey of various, mainly combinatorial, applications of the Subspace Theorem. We take an algebraic approach to most of the problems and use techniques from commutative algebra, incidence geometry, number theory and graph theory. In Chapter 2 we give extensions of a result of Elekes and Rónyai that says that if the graph of a real (or complex) polynomial contains many points of a cartesian product then the polynomial has a special additive or multiplicative form. We extend this to asymmetric cartesian products and to higher dimensions. Elekes and Rónyai’s result was used to prove a conjecture of Purdy on the number of distinct distances between two collinear point sets in the plane. Our extensions give improved bounds for the conjecture. In Chapter 3 we prove a special case of the Erdős unit distance problem. This problem asks for the maximum possible number of unit distances between n points in the plane in the form of an asymptotic upper bound. We provide an upper bound of n^(1+7/sqrt(log(n))) when we only consider unit distancescorresponding to roots of unity and give a superlinear lower bound. We also consider related rational distance problems. We require an algebraic result of Mann on the number of solutions of linear equations of roots of unity. In Chapter 4 we extend our result from the previous chapter to unit distances coming from a multiplicative subgroup of ℂ^* of “low” rank. We usea corollary of the Subspace Theorem. In this case we get, for ε > 0, at most cn^(1+ε) unit distances. We show that the well known lower bound construction of Erdős for the general unit distance problem consists of distances from such a subgroup and so our result applies to the best known maximal unit distance sets. In Chapter 5 we give a survey of various applications of the Subspace Theorem including less well known combinatorial applications such as sum-product estimates and line configurations with few distinct intersections.
This thesis includes three papers and one expository chapter as backgroundfor one of the papers. These papers have in common that they combinealgebra with discrete geometry, mostly by using algebraic tools to provestatements from discrete geometry. Algebraic curves and number theoryalso recur throughout the proofs and results. In Chapter 1, we will detailthese common threads.In Chapter 2, we prove that an infinite set of points in R² such that allpairwise distances are rational cannot be contained in an algebraic curve,except if that curve is a line or a circle, in which case at most 4 respectively 3points of the set can be outside the line or circle. In the proof we use theclassification of curves by their genus, and Faltings' Theorem.In Chapter 3, we informally present an elementary method for computingthe genus of a planar algebraic curve, illustrating some of the techniques inChapter 2.In Chapter 4, we prove a bound on the number of unit distances that canoccur between points of a finite set in R², under the restriction that the linesegments corresponding to these distances make a rational angle with thehorizontal axis. In the proof we use graph theory and an algebraic theoremof Mann.In Chapter 5, we give an upper bound on the length of a simultaneousarithmetic progression (a two-dimensional generalization of an arithmeticprogression) on an elliptic curve, as well as for more general curves. Wegive a simple proof using a theorem of Jarnik, and another proof using theCrossing Inequality and some bounds from elementary algebraic geometry,which gives better explicit bounds.
A framework in Euclidean space consists of a set of points calledjoints, and line segments connecting pairs of joints called bars. Aframework is flexible if there exists a continuous motion of its jointssuch that all pairs of joints with a bar remain at a constant distance, but between at least one pair of joints not joined by a bar, the distance changes. Forexample, a square in the plane is not rigid since it can be deformedinto a family of rhombi. This thesis is mainly concerned with infinitesimal motions. Loosely speaking, a framework is infinitesimally rigid if it does not wobble. One example is a motion of a single joint, where all other joints are unmoving, such that the movement of the one joint is perpendicular to all bars attached to it. The distances in an infinitesimal motion are preserved in the initial instant of motion. Infinitesimally rigidframeworks are rigid, and is an easier quality to verify, thereby making it a popular notion of rigidity to study among engineerings, architects, and mathematicians. We present infinitesimally rigid bipartiteunit-bar frameworks in ℝ^n, and infinitesimally rigidbipartite frameworks in the plane with girth up to 12. Our constructions make use of the knight's graph; a graph such that vertices (joints) are squares of a chessboard and edges (bars) represent legal moves of the knight. We show that copies of the knight's graph can be assembled to create infinitesimally rigid frameworks in any dimension. Our constructions answer questions of Hiroshi Maehara.