Leírás
Véges Geometria szeminárium
Abstract:
Erdős, Füredi, Rothschild and T. Sós initiated the following problem.
Let G(n,e) denote a graph on n vertices and e edges. Fix a positive integer k and a pair of integers (n, e) such that 0< e< \binom{n}{2}. For which t does it hold that
any n-vertex graph with e edges contains an induced subgraph on k vertices having exactly t edges? Equivalently, we are seeking pairs (k,t) such that k-vertex subgraphs with t edges are unavoidable in graphs of the form G(n,e).
We study the q-analogue of this problem.
Let S be a subset of size m of the affine space AG(n,q). Does there always exist a k-dimensional affine subspace which contains exactly t points of S?
We show general bounds on the number of values for m, for which a k-flat is unavoidable with exactly t point for every m-set of AG(n,2).
The bounds are partly relying on the combination of an algebraic (so-called lexicographic) construction and random constructions, partly on supersaturation results.
Joint work with Benedek Kovács (ELTE).