Freiman homomorphisms on sparse random sets

David Conlon, W. T. Gowers

Type: Article

Publication Date: 2017-02-03

Citations: 0

DOI: https://doi.org/10.1093/qmath/haw058

Abstract

A result of Fiz Pontiveros shows that if A is a random subset of ZN 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 ZN⁠. In this paper, we improve the bound to CN−2/3(logN)1/3⁠, which is best possible up to the constant factor.

Locations

arXiv (Cornell University) - View - PDF
Apollo (University of Cambridge) - View - PDF
CaltechAUTHORS (California Institute of Technology) - View - PDF
Oxford University Research Archive (ORA) (University of Oxford) - View - PDF
The Quarterly Journal of Mathematics - View

Similar Works

Action	Title	Year	Authors
+	Freiman homomorphisms on sparse random sets	2016	David Conlon W. T. Gowers
+	Freiman Homomorphisms of Random Subsets of	2013	Gonzalo Fiz Pontiveros
+	Freiman homomorphisms of random subsets of $\mathbb{Z}_{N}$	2010	Gonzalo Fiz Pontiveros
+	Freiman homomorphisms of random subsets of $\mathbb{Z}_{N}$	2010	Gonzalo Fiz Pontiveros
+	Polynomial configurations in subsets of random and pseudo-random sets	2016	Elad Aigner‐Horev Hiệp Hàn
+	A note on random homomorphism from arbitrary graphs to Z	2003	Martin Loebl Jaroslav Nešetřil Bruce Reed
+	Topics in additive combinatorics	2016	Rudi Mrazović
+	A note on Random Homomorphism from ArbitraryGraphs to Z	2001	Martin Loebl Jaroslav Nešetřil Bruce Reed
+ PDF Chat	The Furstenberg set and its random version	2022	Aihua Fan Hervé Queffélec Martine Queffélec
+ PDF Chat	None	2015	Shachar Lovett
+	On pseudo-random subsets of $${\mathbb Z _n}$$	2008	Cécile Dartyge Andràs Sárközy
+ PDF Chat	Random functions in Fourier restriction algebras	1976	Toru Kawai
+ PDF Chat	Homomorphisms of random paths	2009	Gábor Kun Claude Tardif
+	Counting sets with small sumset and applications	2013	Ben Green Robert Morris
+	On constant-multiple-free sets contained in random sets of integers	2014	Sang June Lee
+	Sharp hypercontractivity for symmetric groups and its applications	2023	Peter Keevash Noam Lifshitz
+ PDF Chat	Linear forms and quadratic uniformity for functions on ℤ N	2011	W. T. Gowers Jason B. Wolf
+ PDF Chat	Sumset and Inverse Sumset Theory for Shannon Entropy	2010	Terence Tao
+ PDF Chat	A SIMPLE TIGHTNESS CONDITION FOR RANDOM ELEMENTS ON $ C([0,1]^2) $	1974	Takeaki Nagai
+	Homomorfismos de grafos	2008	Cristiane M. Sato

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (9)

Action	Title	Year	Authors
+ PDF Chat	The infamous upper tail	2002	Svante Janson Andrzej Ruciński
+	None	2011	J.L. Rami ́rez Alfonsi ́n Sándor Z. Kiss Imre Z. Ruzsa Carlos Vinuesa
+	Independent sets in hypergraphs	2014	József Balogh Robert Morris Wojciech Samotij
+ PDF Chat	On the KŁR conjecture in random graphs	2014	David Conlon W. T. Gowers Wojciech Samotij Mathias Schacht
+	Freiman Homomorphisms of Random Subsets of	2013	Gonzalo Fiz Pontiveros
+ PDF Chat	Combinatorial theorems in sparse random sets	2016	David Conlon W. T. Gowers
+ PDF Chat	Hypergraph containers	2015	David Saxton Andrew Thomason
+ PDF Chat	Extremal results for random discrete structures	2016	Mathias Schacht
+	Ramsey properties of random discrete structures	2010	Ehud Friedgut Vojtěch Rödl Mathias Schacht