The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science,biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.

Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.

We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

This thesis is chiefly concerned with a classical conjecture of Littlewood's regarding the L¹-norm of the Fourier transform, and the closely related idem-potent theorem. The vast majority of the results regarding these problems are, in some sense, qualitative or at the very least infinitary and it has become increasingly apparent that a quantitative state of affairs is desirable. Broadly speaking, the first part of the thesis develops three new tools for tackling the problems above: We prove a new structural theorem for the spectrum of functions in A(G); we extend the notion of local Fourier analysis, pioneered by Bourgain, to a much more general structure, and localize Chang's classic structure theorem as well as our own spectral structure theorem; and we refine some aspects of Freiman's celebrated theorem regarding the structure of sets with small doubling. These tools 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 situation varies wildly with the underlying group and we pay special attention first to the finite field case (where we use Chang's Theorem) and then to the case of residues modulo a prime where we require our new local structure theorem for A(G). We complete the consideration of Littlewood's problem for finite abelian groups by using the local version of Chang's Theorem we have developed. Finally we deploy the Freiman tools along with the extended Fourier analytic techniques to yield a fully quantitative version of the idempotent theorem.

<p>Studying properties of random polynomials has marked a shift in algebraic geometry. Instead of worst-case analysis, which often leads to overly pessimistic perspectives, randomness helps perform average-case analysis, and thus obtain a more realistic view. Also, via Erdos' astonishing 'probabilistic method', one can potentially obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness. </p> <p><br></p> <p>In this thesis, we study topological questions in real algebraic geometry, o-minimal geometry and random algebraic geometry, with motivation from incidence combinatorics. Specifically, we prove results along two different threads:</p> <p><br></p> <p>1. Topology of semi-algebraic and definable (over any o-minimal structure over R) sets, in both deterministic and random settings.</p><p>2. Topology of random hypersurface arrangements. In this case, we also prove a result that could be of independent interest in random graph theory.</p> <p><br></p> <p>Towards the first thread, motivated by applications in o-minimal incidence combinatorics, we prove bounds (both deterministic and random) on the topological complexity (as measured by the Betti numbers) of general definable hypersurfaces restricted to algebraic sets. Given any sequence of hypersurfaces, we show that there exists a definable hypersurface G, and a sequence of polynomials, such that each manifold in the sequence of hypersurfaces appears as a component of G restricted to the zero set of some polynomial in the sequence of polynomials. This shows that the topology of the intersection of a definable hypersurface and an algebraic set can be made <i>arbitrarily pathological</i>. On the other hand, we show that for random polynomials, the Betti numbers of the restriction of the zero set of a random polynomial to any definable set deviates from a Bezout-type bound with <i>bounded probability</i>.</p> <p><br></p> <p>Progress in o-minimal incidence combinatorics has lagged behind the developments in incidence combinatorics in the algebraic case due to the absence of an o-minimal version of the Guth-Katz <i>polynomial partitioning</i> theorem, and the first part of our work explains why this is so difficult. However, our average result shows that if we can prove that the measure of the set of polynomials which satisfy a certain property necessary for polynomial partitioning is suitably bounded from below, by the <i>probabilistic method</i>, we get an o-minimal polynomial partitioning theorem. This would be a tremendous breakthrough and would enable progress on multiple fronts in model theoretic combinatorics. </p> <p><br></p> <p>Along the second thread, we have studied the average Betti numbers of <i>random hypersurface arrangements</i>. Specifically, we study how the average Betti numbers of a finite arrangement of random hypersurfaces grows in terms of the degrees of the polynomials in the arrangement, as well as the number of polynomials. This is proved using a random Mayer-Vietoris spectral sequence argument. We supplement this result with a better bound on the average Betti numbers when one considers an <i>arrangement of quadrics</i>. This question turns out to be equivalent to studying the expected number of connected components of a certain <i>random graph model</i>, which has not been studied before, and thus could be of independent interest. While our motivation once again was incidence combinatorics, we obtained the first bounds on the topology of arrangements of random hypersurfaces, with an unexpected bonus of a result in random graphs.</p>

If <i>E</i> is an exterior algebra on a finite dimensional vector space and <i>M</i> is a graded <i>E</i>-module, the relationship between the resonance varieties of <i>M</i> and the minimal free resolution of <i>M </i>is studied. In the context of Orlik–Solomon algebras, we give a condition under which elements of the second resonance variety can be obtained. We show that the resonance varieties of a general <i>M</i> are invariant under taking syzygy modules up to a shift. As corollary, it is shown that certain points in the resonance varieties of <i>M</i> can be determined from minimal syzygies of a special form, and we define syzygetic resonance varieties to be the subvarieties consisting of such points. The (depth one) syzygetic resonance varieties of a square-free module <i>M</i> over <i>E</i> are shown to be subspace arrangements whose components correspond to graded shifts in the minimal free resolution of <i>_SM</i>, the square-free module over a commutative polynomial ring <i>S </i>corresponding to <i>M</i>. Using this, a lower bound for the graded Betti numbers of the square-free module<i> M</i> is given. As another application, it is shown that the minimality of certain syzygies of Orlik–Solomon algebras yield linear subspaces of their (syzygetic) resonance varieties and lower bounds for their graded Betti numbers.

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)