Graduate Theoretical Computer Science and Combinatorics Seminar
Stoyan Dimitrov
UIC
On the Problem of Power-Free Subsets
Abstract: In 1965, Paul Erdos easily proved that if $S$ is a finite set of nonzero real
numbers, then there exists a sum-free subset $S' \subseteq S$ such that
$|S'| \ge \frac{1}{3}|S|.$ Here, a sum-free subset $S$ is such that there is
no triple of elements $a, b, c$ in $S$ for which $a + b = c.$
Eberhard, Green and Manners proved in 2013 that the same is not true for
a constant bigger than $\frac{1}{3}$, i.e. $\frac{1}{3}$ is the biggest
possible constant with this property. Here, we consider the analogous problem
where triples $a, b, c$ in $S$ for which $a^b = c$ are forbidden. We show that
$\frac{1}{8}$ is a lower bound for the optimal constant (private communication
with Noga Alon), as well as that $\frac{1}{2}$ is an upper bound for it.
Tuesday October 22, 2019 at 5:00 PM in 512 SEO