Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Large Sets Avoiding Prescribed Differences
Speaker: Paul Raff, Rutgers University
Date: Thursday, February 5, 2009 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, I will discuss the quantity f(n,D), which is defined as the size of the largest subset of [n] that avoids differences prescribed in the set D. This quantity was first considered implicitly in a early-1980s paper of Peter Shor where he produced a counterexample of the short-lived Triangle Conjecture of Pierre and Schutzenberger. The quantity f(n,D) additionally has meaningful interpretations in graph theory and in combinatorics on words.
I will begin with the history of the Triangle Conjecture and Shor's counterexample, and I will then start with a simple recurrence involving f(n,D) and use it to derive plenty of information regarding the structure of the sequence {f(n,D)} as n goes from 1 to infinity. Although the problem of finding the quantity f(n,D) exactly is NP-hard, I will show that the quantity f(n,D)/n converges to a constant alpha(D) as n goes to infinity. I will also discuss three different variations of f(n,D) and demonstrate computer software and exact results corresponding to certain values of D.
No deep prior knowledge is necessary for this talk, and a lot of open questions will be posed, including a modified version of the Triangle Conjecture stated in terms of f(n,D). This is an accumulation of work over the past year with Prof. Doron Zeilberger.