DescriptionThis thesis centers around two major projects that I have undertaken in the subject of discrete mathematics. The first project, discussed in Chapters 3-7, pertains to the stable matching problem, and puts particular focus on a relaxation of the notion of stability that we call S-stability. The second project, which appears in Chapters 8 and 9, looks at the properties of boolean functions as polynomials.
The stable matching problem is a well-known problem in discrete mathematics; a full background on the topic appears in Chapter 2. Our investigations into the stable matching problem center around the operation psi:E(G(I))ightarrow E(G(I)), which we establish a framework for in Chapter 3 and define in Chapter 4; we show that for sufficiently large k, psi_I^k maps everything to a set of edges that we call the hub, and give algorithms for evaluating psi_I(S) for specific values of S. In later chapters, we extend results on the lattice structure of stable matchings to the discussed weaker notions of stability (Chapter 5) and consider the polytope of fractional matchings for these same weaker notions (Chapter 6). We also reflect on graphs represented by instances with every edge in the hub (Chapter 7).
It is well known that any boolean function f:{0,1}^nightarrow{0,1} can be represented as a unique multilinear polynomial. In Chapter 8, we consider a sensitivity measure that we call the maxonomial hitting set size, and apply it in order to improve a result by Nisan and Szegedy on the maximum number of variables in a low degree boolean polynomial (Cref{thm:main}).footnote{This section was previously published on ArXiv in 2018, and was published in Combinatorica earlier this year cite{CHS19}.} In Chapter 9, we focus on expanding our understanding of the largest possible maxonomial hitting set size for a degree d boolean function.