Leírás
Given an m-element subset S of F_2^n, is there guaranteed to be a (k,t)-flat, i.e. a k-dimensional affine subspace of F_2^n containing exactly t points of S? With Zoltán Lóránt Nagy, we have investigated this question and conjectured that the answer is yes for almost all values of m in the interval [0, 2^n] as n tends to infinity. Building on a result of Bonin and Qin, we proved this when t∈{0, 2^{k-1}, 2^k}.
This talk focuses on the smallest open case of the conjecture, (k,t)=(3,1). So we are interested in giving (3,1)-flat-avoiding subsets in F_2^n of various sizes. A random method built on Guruswami's ideas gives that it is possible to avoid (3,1)-flats for m very close to 2^n. We now present a new framework for creating explicit constructions of such sets S via binary linear codes, raising interesting questions about second-order Reed-Muller codes and weight enumerator polynomials.