Freiman homomorphisms on sparse random sets

DOI10.1093/QMATH/HAW058MaRDI QIDQ2987024zbMATH OpenOpenAlexFDO

Authors David Conlon, W. Timothy Gowers

Publication date 17 May 2017

Published in The Quarterly Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.01734, https://authors.library.caltech.edu/97841/

zbMATH Keywords

binomial random modelextremal problemsFreiman homomorphism

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: A result of Fiz Pontiveros shows that if $A$ is a random subset of $mathbb{Z}_N$ where each element is chosen independently with probability $N^{-1/2+o(1)}$, then with high probability every Freiman homomorphism defined on $A$ can be extended to a Freiman homomorphism on the whole of $mathbb{Z}_N$. In this paper we improve the bound to $C{N}^{-2/3}(logN{)}^{1/3}$, which is best possible up to the constant factor.

Recommendations

• Freiman homomorphisms of random subsets of Z_N
• Freiman's theorem in finite fields via extremal set theory
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• On the Freiman theorem in finite fields
• Polynomial configurations in subsets of random and pseudo-random sets

Cited in

(1)

• Freiman homomorphisms of random subsets of Z_N

This page was built for publication: Freiman homomorphisms on sparse random sets

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