About sunflowers

arXiv1804.10050MaRDI QIDQ6300844FDOQ6300844

Authors: Gábor Hegedüs 

Publication date: 26 April 2018

Abstract: Alon, Shpilka and Umans considered the following version of usual sunflower-free subset: a subset $$cal F$$ for $D>2$ is sunflower-free if for every distinct triple $$cal F$$ there exists a coordinate $i$ where exactly two of $x_i,y_i,z_i$ are equal. Combining the polynomial method with character theory Naslund and Sawin proved that any sunflower-free set $$cal F$$ has size ${\displaystyle }$ |mbox{$calF$}|leq c_D^n, ${\displaystyle }$ where $c_D=frac32^{2/3}(D-1{)}^{2/3}$. In this short note we give a new upper bound for the size of sunflower-free subsets of ${1,ldots,D}^n$. Our main result is a new upper bound for the size of sunflower-free $k$-uniform subsets. More precisely, let $k$ be an arbitrary integer. Let $$cal F$$ be a sunflower-free $k$-uniform set system. Consider $$cal F$$ Then ${\displaystyle }$ |mbox{$calF$}|leq 3(lceilfrac{2k}{3} ceil+1)(2^{1/3}cdot 3e)^k(lceilfrac Mk ceil -1)^{lceilfrac{2k}{3} ceil}. ${\displaystyle }$ In the proof we use Naslund and Sawin's result about sunflower-free subsets in ${1,ldots,D}^n$.

Mathematics Subject Classification ID

Other combinatorial set theory (03E05) Combinatorial aspects of packing and covering (05B40) Extremal set theory (05D05)

This page was built for publication: About sunflowers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300844)