A few combinatorial problems

### Citation & ExportHide

#### Simple citation

Berkowitz, Ross.

**A few combinatorial problems.**Retrieved from https://doi.org/doi:10.7282/T3KS6VHN#### Export

### StatisticsHide

### Description

TitleA few combinatorial problems

NameBerkowitz, Ross (author); Kopparty, Swastik (chair); Kahn, Jeff (internal member); Zeilberger, Doron (internal member); O'Donnell, Ryan (outside member); Rutgers University; Graduate School - New Brunswick

Date Created2017

Other Date2017-05 (degree)

SubjectMathematics, Combinatorial analysis

Extent1 online resource (viii, 102 p. : ill.)

DescriptionThis thesis studies three problems in combinatorics. Our first result is a quantitative local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), for a fixed p ∈ (0, 1). This proof is an extension of the previous work of Gilmer and Kopparty, who proved that the local limit theorem held asymptotically for triangles. Our work gives bounds on the l1 and l∞ distance of the triangle distribution from a suitable discrete normal.

In our second result we prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix, and let P denote the set of n × n matrices that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ kAk n 2 with equality iff A/kAk2 ∈ P (where kAk2 is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than kAk n 2 . In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than kAk n 2 unless all but at most αn rows contain entries of modulus at least kAk2(1 − β).

Finally, we construct large sequences with the property that the contents of any small window determine the location of the window, robustly. Such objects have found ii many applications in practical settings, from positioning of wireless devices to smart pens, and have recently gained some theoretical interest. In this context, we give the first explicit constructions of sequences with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.

In our second result we prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix, and let P denote the set of n × n matrices that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ kAk n 2 with equality iff A/kAk2 ∈ P (where kAk2 is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than kAk n 2 . In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than kAk n 2 unless all but at most αn rows contain entries of modulus at least kAk2(1 − β).

Finally, we construct large sequences with the property that the contents of any small window determine the location of the window, robustly. Such objects have found ii many applications in practical settings, from positioning of wireless devices to smart pens, and have recently gained some theoretical interest. In this context, we give the first explicit constructions of sequences with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.

NotePh.D.

NoteIncludes bibliographical references

Noteby Ross Berkowitz

Genretheses

Persistent URLhttps://doi.org/doi:10.7282/T3KS6VHN

Languageeng

CollectionGraduate School - New Brunswick Electronic Theses and Dissertations

Organization NameRutgers, The State University of New Jersey

RightsThe author owns the copyright to this work.