UC San Diego

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$.