LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
Abstract
This 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.
Subject (authority = local)
Topic
Boolean functions
Subject (authority = RUETD)
Topic
Mathematics
RelatedItem (type = host)
TitleInfo
Title
Rutgers University Electronic Theses and Dissertations
Identifier (type = RULIB)
ETD
Identifier
ETD_11208
PhysicalDescription
Form (authority = gmd)
InternetMediaType
application/pdf
InternetMediaType
text/xml
Extent
1 online resource (vi, 179 pages)
Note (type = degree)
Ph.D.
Note (type = bibliography)
Includes bibliographical references
Genre (authority = ExL-Esploro)
ETD doctoral
RelatedItem (type = host)
TitleInfo
Title
School of Graduate Studies Electronic Theses and Dissertations
Identifier (type = local)
rucore10001600001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
I hereby grant to the Rutgers University Libraries and to my school the non-exclusive right to archive, reproduce and distribute my thesis or dissertation, in whole or in part, and/or my abstract, in whole or in part, in and from an electronic format, subject to the release date subsequently stipulated in this submittal form and approved by my school. I represent and stipulate that the thesis or dissertation and its abstract are my original work, that they do not infringe or violate any rights of others, and that I make these grants as the sole owner of the rights to my thesis or dissertation and its abstract. I represent that I have obtained written permissions, when necessary, from the owner(s) of each third party copyrighted matter to be included in my thesis or dissertation and will supply copies of such upon request by my school. I acknowledge that RU ETD and my school will not distribute my thesis or dissertation or its abstract if, in their reasonable judgment, they believe all such rights have not been secured. I acknowledge that I retain ownership rights to the copyright of my work. I also retain the right to use all or part of this thesis or dissertation in future works, such as articles or books.