Home
Resource
Some combinatorial results on matrices and polynomials
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(541.28 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Semonsen, Justin. Some combinatorial results on matrices and polynomials. Retrieved from https://doi.org/doi:10.7282/t3-a5pa-d134

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleSome combinatorial results on matrices and polynomials
NameSemonsen, Justin (author); Kopparty, Swastik (chair); Saraf, Shubhangi (internal member); Narayanan, Bhargav (internal member); Srinivasan, Srikanth (outside member); Rutgers University; School of Graduate Studies
Date Created2020
Other Date2020-05 (degree)
SubjectMathematics
Extent1 online resource (viii, 48 pages)
DescriptionThis thesis studies three problems in combinatorics that concern matrices and polyno- mials.

The first problem refines a technique by Scheinerman [24] to get an improved upper bound on the determinants of n×n 0-1 matrices with k ones in each row. Our new bound uses linear programming techniques to analyze a greedy decomposition algorithm, show how it improves on previous methods, and determine its asymptotic behavior as a function of k. We also present and analyze an improvement to this method, as well as the limitations and other possibilities of using this technique.

The second problem analyzes the supports of F2 polynomials on n variables in Ham- ming balls, and proves an optimal Schwartz-Zippel-like bound. We then use methods based on those of Kasami and Tokura [11], [12] to find and classify all tight polynomi- als for this bound. Our result is based on studying necessary conditions for ”division lemmas” for polynomials.

The third result studies sets of points in F2^n for which the sum of any F2 polynomial of degree d on those points is 0. We prove that for d ≥ 2, we have that the size of the set must at least twice the affine dimension of the set. For larger d, we can show the size of the set must be a constant amount larger than twice the affine dimension, but we conjecture that this can be improved to 2^(d+1)/(d+2) times the affine dimension of the set. We also apply these theorems to prove a bound on the weight distribution of Reed-Muller codes of high dimension.
NotePh.D.
NoteIncludes bibliographical references
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/t3-a5pa-d134
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024