Upper bounds on Ramsey numbers for vector spaces over finite fields

EUROCOMB’23

Bryce Frederickson Liana Yepremyan

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-062

PDF
Abstract
For $B \subseteq \mathbb F_q^m$, let $\mathrm{ex}_{\mathrm{aff}}(n,B)$ denote the maximum cardinality of a set $A \subseteq \mathbb F_q^n$ with no subset which is affinely isomorphic to $B$. Furstenberg and Katznelson proved that for any $B \subseteq \mathbb F_q^m$, $\mathrm{ex}_{\mathrm{aff}}(n,B)=o(q^n)$ as $n \to \infty$. For certain $q$ and $B$, some more precise bounds are known. We connect some of these problems to certain Ramsey-type problems, and obtain some new bounds for the latter. For $s,t \geq 1$, let $R_q(s,t)$ denote the minimum $n$ such that in every red-blue coloring of one-dimensional subspaces of $\mathbb F_q^n$, there is either a red $s$-dimensional subspace of $\mathbb F_q^n$ or a blue $t$-dimensional subspace of $\mathbb F_q^n$. The existence of these numbers is implied by the celebrated theorem of Graham, Leeb, Rothschild. We improve the best known upper bounds on $R_2(2,t)$, $R_3(2,t)$, $R_2(t,t)$, and $R_3(t,t)$.

Pages:
450–456
References

N. Alon and J. H Spencer, The probabilistic method, John Wiley & Sons, 2016.

J. E Bonin and H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Mathematics 224 (2000), no. 1-3, 37-60.
https://doi.org/10.1016/S0012-365X(00)00108-4

R. C. Bose and R. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and the MacDonald codes, Journal of Combinatorial Theory 1 (1966), no. 1, 96-104.
https://doi.org/10.1016/S0021-9800(66)80007-8

E. Croot, V. F Lev, and P. P. Pach, Progression-free sets in are exponentially small, Annals of Mathematics (2017), 331-337.
https://doi.org/10.4007/annals.2017.185.1.7

J. S Ellenberg and D. Gijswijt, On large subsets of with no three-term arithmetic progression, Annals of Mathematics (2017), 339-343.
https://doi.org/10.4007/annals.2017.185.1.8

J. Fox and L. Lovász, A tight bound for Green's arithmetic triangle removal lemma in vector spaces, Proceedings of the twenty-eighth annual acm-siam symposium on discrete algorithms, 2017, pp. 1612-1617.
https://doi.org/10.1137/1.9781611974782.106

J. Fox and H. T. Pham, Popular progression differences in vector spaces II (2017).

H. Furstenberg and Y. Katznelson, An ergodic Szemerédi theorem for IP-systems and combinatorial theory, Journal d'Analyse Mathématique 45 (1985), no. 1, 117-168.
https://doi.org/10.1007/BF02792547

H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, Journal d'Analyse Mathématique 57 (1991), no. 1, 64-119.
https://doi.org/10.1007/BF03041066

J. Geelen and P. Nelson, An analogue of the Erdős-Stone theorem for finite geometries, Combinatorica 35 (2015), 209-214.
https://doi.org/10.1007/s00493-014-2952-3

D. Gijswijt, Excluding affine configurations over a finite field, arXiv preprint arXiv:2112.12620 (2021).

R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey's theorem for a class of categories, Advances in Math. 8 (1972), 417-433. MR306010
https://doi.org/10.1016/0001-8708(72)90005-9

A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222-229. MR143712
https://doi.org/10.1090/S0002-9947-1963-0143712-1

P. Nelson and K. Nomoto, The structure of claw-free binary matroids, Journal of Combinatorial Theory, Series B 150 (2021), 76-118.
https://doi.org/10.1016/j.jctb.2021.04.002

D. Polymath, A new proof of the density Hales-Jewett theorem, Annals of Mathematics (2012), 1283-1327.
https://doi.org/10.4007/annals.2012.175.3.6

V Rödl, E Tengan, M Schacht, and N Tokushige, Density theorems and extremal hypergraph problems, Israel Journal of Mathematics 152 (2006), no. 1, 371-380.
https://doi.org/10.1007/BF02771992

T. Sanders, Green's sumset problem at density one half, Acta Arithmetica 146 (2011), no. 1, 91-101 (eng).
https://doi.org/10.4064/aa146-1-6

J. H. Spencer, Ramsey's theorem for spaces, Trans. Amer. Math. Soc. 249 (1979), no. 2, 363-371. MR525678
https://doi.org/10.1090/S0002-9947-1979-0525678-7

A. D Taylor, Bounds for the disjoint unions theorem, Journal of Combinatorial Theory, Series A 30 (1981), no. 3, 339-344.
https://doi.org/10.1016/0097-3165(81)90031-5

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Bryce Frederickson, Liana Yepremyan

PDF