Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 11, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Lenny Fukshansky (Claremont McKenna College)
Let N > 1 be an integer, and let 1 < a_1 < ... < a_N be relatively prime integers. Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be represented as a linear combination of a_1,...,a_N with non-negative integer coefficients. More generally, the s-Frobenius number is defined to be the largest positive integer that has precisely s distinct representations like this, so that the classical Frobenius number can be thought of as the 0-Frobenius number. The condition that a_1,...,a_N are relatively prime implies that s-Frobenius numbers exist for every non-negative integer s. The general problem of determining the Frobenius number, given N and a_1,...,a_N, dates back to the 19-th century lectures of G. Frobenius and work of J. Sylvester, and has been studied extensively by many prominent mathematicians of the 20-th century, including P. Erdos. While this problem is now known to be NP-hard, there has been a number of successful efforts by various authors producing bounds and asymptotic estimates on the Frobenius number and its generalization. I will discuss some of these results, which are obtained by an application of techniques from Discrete Geometry.
Automatic MiSe System Software Version 1.4803M | admin login