Bounds on extremal functions of forbidden patterns

Extremal functions of forbidden sequences and 0 - 1 matrices have applications to many problems in discrete geometry and enumerative combinatorics. We present a new computational method for deriving upper bounds on extremal functions of forbidden sequences. Then we use this method to prove tight bounds on the extremal functions of sequences of the form (12 ... 1)t for 1 >/= 2 and t >/= 1, abc(acb)t for t >/= 0, and avav'a, such that a is a letter, v is a nonempty sequence excluding a with no repeated letters and v' is obtained from v by only moving the first letter of v to another place in v. We also prove the existence of infinitely many forbidden 0 - 1 matrices P with non-linear extremal functions for which every strict submatrix of P has a linear extremal function. Then we show that for every d-dimensional permutation matrix P with k ones, the maximum number of ones in a d-dimensional matrix of sidelength n that avoids P is 20(k) nd-1

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Geneson, Jesse (Jesse T.)

Advisor dc:contributor.advisor

• Peter Shor.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99069

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99069