COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Two Problems in Discrete Mathematics
by Chiarelli, John, Ph.D., Rutgers The State University of New Jersey, School of Graduate Studies, 2020, 186; 28149740
Abstract (Summary)

This thesis centers around two projects that I have undertaken in the subject of discrete mathematics. The primary project pertains to the stable matching problem, and puts particular focus on a relaxation of stability that we call S-stability. The secondary project looks at boolean functions as polynomials, and seeks to understand and use a complexity measure called the maxonomial hitting set size.

The stable matching problem is a well-known problem in discrete mathematics, with many practical applications for the algorithms derived from it. Our investigations into the stable matching problem center around the operation ψ : E(G(I)) → E(G(I)); we show that for sufficiently large k, ψIk maps everything to a set of edges that we call the hub, and give algorithms for evaluating ψI(S) for specific values of S. Subsequently, we extend results on the lattice structure of stable matchings to S-stability and consider the polytope of fractional matchings for these same weaker notions of stability. We also reflect on graphs represented by instances with every edge in the hub.

Given a boolean function f : {0, 1}n → {0, 1}, it is well-known that it can be represented as a unique multilinear polynomial. We improve a result by Nisan and Szegedy on the maximum number of relevant variables in a low degree boolean polynomial using the maxonomial hitting set size, and look at the largest possible maxonomial hitting set size for a degree d boolean function.

Indexing (document details)
Advisor: Saks, Michael
Commitee: Zeilberger, Doron
School: Rutgers The State University of New Jersey, School of Graduate Studies
Department: Mathematics
School Location: United States -- New Jersey
Source: DAI-B 82/7(E), Dissertation Abstracts International
Subjects: Mathematics
Keywords: Boolean functions, Stable matching problem
Publication Number: 28149740
ISBN: 9798557093286
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy