This dissertation consists of two parts. First, we define and study positional marked patterns. A positional marked pattern tau is a permutation where one of elements in tau is underlined. Given a permutation sigma, we say that sigma_i is tau-match at position i if tau occurs in sigma in such a way that sigma_i plays the role of the underlined element in the occurrence. We let pmp_tau(sigma) denote the number of position i which sigma is tau-match. This defines a new class of statistics on permutations, where we study such statistics and prove a number of results. In particular, we prove that two positional marked patterns (1)23 and (1)32 give rise to two statistics that have the same distribution. The equidistibution phenomenon also occurs in other several pairs of patterns like 1(2)3 and 1(3)2, which we prove in this dissertation. The second part of the dissertation focuses on the Whitney numbers of Dowling lattices. In the papers [2, 3], Benoumhani defined two polynomials Fm,n,1(x)

and Fm,n,2(x). Then, he defined Am(n,k) and Bm(n,k) to be the polynomials satisfying

Fm,n,1(x) = Sum_k=0^n Am(n,k)x^(n-k)(x+1)^k

and

Fm,n,2(x) = Sum_k=0^n Bm(n,k)x^(n-k)(x+1)^k.

In this dissertation, we give a combinatorial interpretation of coefficients of Am+1(n,k) and prove a symmetry of the coefficients, namely Am+1(n,k)|m^s = Am+1(n,n-k)|m^(n-s). We also give a combinatorial interpretation of Bm+1(n,k), prove that Bm+1(n,n-1) is a polynomial in m with non-negative integer coefficients, and prove that Bm+1(n,n-2) is a polynomial in m with non-negative integer coefficients except for the coefficient of m^(n-1) which is -(n-1) for n >=6.

This dissertation lies at the intersection of extremal combinatorics and probabilistic combinatorics. Roughly speaking, \textit{extremal combinatorics} studies how large a combinatorial object can be. For example, a classical result of Mantel's says that every $n$-vertex triangle-free graph has at most $\quart n^2$ edges. The area of \textit{probabilistic combinatorics} encompasses both the application of probability to combinatorial problems, as well as the study of random combinatorial objects such as random graphs and random permutations. In this dissertation we study three problems related to extremal properties of random objects. First, we study the maximum score of a certain guessing game which uses a randomly shuffled deck of cards, and in doing so we solve a 40 year conjecture of Diaconis and Graham. Next, we study the Tur an problem in random hypergraphs. Specifically, we examine the function $\ex(H_{n,p}^r,\c{F})$, which is the maximum number of hyperedges that an $\c{F}$-free subgraph of the random hypergraph $H_{n,p}^r$ can have. By using a novel counting technique, we obtain effective bounds when $\c{F}$ consists of a collection of Berge cycles. Finally, we study thresholds of random graphs and hypergraphs, which essentially asks how large $p$ must be in order for $H_{n,p}^r$ to contain a given structure. We give a common generalization of recent breakthrough work done by Alweiss, Lovett, Wu, and Zhang related to the Erd\H{o}s sunflower problem; and of work by Kahn, Narayanan, and Park related to the threshold for squares of Hamiltonian cycles in $G_{n,p}$.

This thesis studies problems in extremal graph theory, combinatorial number theory, and finite incidence geometry, and the interplay between these three areas.

The first topic is the study of the Tur an number for $C_4$. F\"uredi showed that $C_4$-free graphs with $\mathrm{ex}(n, C_4)$ edges are intimately related to polarity graphs of projective planes. We prove a general theorem about dense subgraphs in a wide class of polarity graphs, and as a result give the best-known lower bounds for $\mathrm{ex}(n, C_4)$ for many values of $n$. We also study the chromatic and independence numbers of polarity graphs, with special emphasis on the graph $ER_q$.

Next we study Sidon sets on graphs by considering what sets of integers may look like when certain pairs of them are restricted from having the same product. Other generalizations of Sidon sets are considered as well.

We then use $C_4$-free graphs to prove theorems related to solvability of equations. Given an algebraic structure $R$ and a subset $A\subset R$, define the {\em sum set} and {\em product set} of $A$ to be $A+A = \{a+b:a,b\in A\}$ and $A\cdot A = \{a\cdot b: a,b\in A\}$ respectively. Showing under what conditions at least one of $|A+A|$ or $|A\cdot A|$ is large has a long history of study that continues to the present day. Using spectral properties of the bipartite incidence graph of a projective plane, we deduce that nontrivial sum-product estimates hold in the setting where $R$ is a finite quasifield. Several related results are obtained.

Finally, we consider a classical question in finite incidence geometry: what is the subplane structure of a projective plane? A conjecture widely attributed to Neumann is that all non-Desarguesian projective planes contain a Fano subplane. By studying the structural properties of polarity graphs of a projective plane, we show that any plane of even order $n$ which admits a polarity such that the corresponding polarity graph has exactly $n+1$ loops must contain a Fano subplane. The number of planes of order up to $n$ which our theorem applies to is not bounded above by any polynomial in $n$.

In this dissertation, we examine various problems in extremal set theory, which typically entails maximizing the size of a collection of subsets, or set family, given intersection constraints. For instance, the classical Erd{\H o}s-Ko-Rado theorem (1961) establishes the largest set family of size $k$ subsets of an $n$ element set which is {\it intersecting} (i.e. has the property that any two sets have at least one element in common). The largest such intersecting family is the collection of all size $k$ subsets that contain a fixed element, which is commonly referred to as {\it the star}. Answering a question of Erd{\H o}s, Ko and Rado, Hilton and Milner (1967) determined the largest intersecting set family which is not isomorphic to a sub-collection of the star. This dissertation settles a conjecture of Hilton and Milner (1967) on the largest set family, for each integer $d \geq 3$, of size $k$ subsets of an $n$ element set which has the property that any $d$ sets have at least one element in common and is not isomorphic to a sub-collection of the star. We also consider various combinatorial results on set families with restricted intersection properties. In particular, we prove generalizations of both the {\it Bollob{ a}s two family} theorem and the {\it Oddtown and Eventown} theorems.

In this dissertation, we study problems concerning independent sets in hypergraphs. We try to determine the minimum independence number of a hypergraph in a certain family of hypergraphs. In Chapter 1, we introduce history of this kind of problems.

In Chapter 2, we analyze the outcome of a randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth. We show that the expected size of the output independent sets can be expressed as the solution of some differential equations and show that it is concentrated around its mean.

In Chapter 3, we establish an upper bound for the Ramsey numbers for nontrivial Berge cycles of even length and prove that this bound is essentially tight if a conjecture of Erd\"os and Simonovits is true.

In Chapter 4, we show an upper bound for the Ramsey numbers for 3-uniform loose 4-cycle, improving previous result on this problem.

In Chapter 5, we find a lower bound for the maximum size of a loose triangle-free subgraph in a uniform hypergraph in terms of its maximum degree. Moreover, we determine the magnitude of the maximum size of a loose triangle-free subgraph in the uniform random hypergraph.

In this dissertation we study juggling card sequences and edge flipping in graphs, as well as some related problems. Juggling patterns can be described by a sequence of cards which keep track of the relative order of the balls at each step. This interpretation has many algebraic and combinatorial properties, and we place particular focus on discovering connections between this model and other studied structures and sequences. We begin with the juggling card properties of traditional juggling patterns, and their enumerative connections to Stirling numbers. We then study the case where multiple balls are thrown at once, a problem with connections to arc-labeled digraphs and boson normal ordering. Next we examine crossings in juggling cards. The first such case connects neatly to Dyck paths and Narayana numbers, while the later cases require new approaches. Lastly we examine a randomized model of juggling.

Edge flipping in graphs is a randomized coloring process on a graph. In particular: fix a graph $G$ and repeatedly choose an edge from $E(G)$ (uniformly at random, with replacement). After each selection, with probability $p$ color the vertices of the edge blue; otherwise color these vertices red. This induces a well-behaved random walk on the state space of all red/blue colorings of the complete graph and so has a stationary distribution. We derive this stationary distribution for the complete graph. We then study more classes of graphs and asymptotics of some special cases. We conclude with two related problems. First we study graph builds, which is a graph construction interpretation of edge flipping which has recently garnered interest in its own right. We then introduce hyperedge flipping in $t$-uniform hypergraphs and discuss some future work.

We address several problems in spectral graph theory, with a common theme of optimizing or computing a spectral graph invariant, such as the spectral radius or spectral gap, over some family of graphs. In particular, we study measures of graph irregularity, we bound the adjacency spectral radius over all outerplanar and planar graphs, and finally we determine the spectral gap of reversal graphs and a family of graphs that generalize the prefix reversal graph.

Firstly we study two measures of graph irregularity, the principal ratio and the difference between the spectral radius of the adjacency matrix and the average degree. For the principal ratio, we show that the graphs which maximize this statistic are the kite graphs, which are a clique with a pendant path, when the number of vertices is sufficiently large. This answers a conjecture of Cioabă and Gregory. For the second graph irregularity measure, we show that the connected graphs which maximize it are pineapple graphs, answering a conjecture of Aouchiche et al.

Secondly we investigate the maximum spectral radius of the adjacency matrix over all graphs on n vertices within certain well-known graph families. Our main result is showing that the planar graph on n vertices with maximal adjacency spectral radius is the join P 2 + P n−2 , when n is sufficiently large. This was conjectured by Boots and Royle. Additionally, we identify the outerplanar graph with maximal spectral radius, answering a conjecture of Cvetkovic̀ and Rowlinson.

Finally, we determine the spectral gap of various Cayley graphs of the symmetric group Sn , which arise in the context of substring reversals. This includes an elementary proof that the prefix reversal (or pancake flipping graph) has spectral gap one, originally

proved via representation theory by Cesi. We generalize this by showing that a large family of related graphs all have unit spectral gap.