{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:42:03Z","timestamp":1648942923262},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T00:00:00Z","timestamp":1370908800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Given a set <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096354831300014X_inline3\" \/><jats:tex-math>$A\\subset\\mathbb{Z}_{N}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we say that a function <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S096354831300014X_inline4\" \/><jats:tex-math>$f\\colon A \\to \\mathbb{Z}_{N}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a <jats:italic>Freiman homomorphism<\/jats:italic> if <jats:italic>f(a)<\/jats:italic>+<jats:italic>f(b)<\/jats:italic>=<jats:italic>f(c)<\/jats:italic>+<jats:italic>f(d)<\/jats:italic> whenever <jats:italic>a,b,c,d<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic> satisfy <jats:italic>a+b<\/jats:italic>=<jats:italic>c+d<\/jats:italic>. This notion was introduced by Freiman in the 1970s, and plays an important role in the field of additive combinatorics. We say that <jats:italic>A<\/jats:italic> is linear if the only Freiman homomorphisms are functions of the form <jats:italic>f(x)<\/jats:italic> = <jats:italic>ax+b<\/jats:italic>.<\/jats:p><jats:p>Suppose the elements of <jats:italic>A<\/jats:italic> are chosen independently at random, each with probability <jats:italic>p<\/jats:italic>. We shall look at the following question: For which values of <jats:italic>p<\/jats:italic>=<jats:italic>p(N)<\/jats:italic> is <jats:italic>A<\/jats:italic> linear with high probability as <jats:italic>N<\/jats:italic> \u2192 \u221e? We show that if <jats:italic>p<\/jats:italic>=(2log<jats:italic>N<\/jats:italic> \u2212 \u03c9(<jats:italic>N<\/jats:italic>))<jats:sup>1\/3<\/jats:sup><jats:italic>N<\/jats:italic><jats:sup>\u22122\/3<\/jats:sup>, where \u03c9(<jats:italic>N<\/jats:italic>) \u2192 \u221e as <jats:italic>N<\/jats:italic> \u2192 \u221e, then <jats:italic>A<\/jats:italic> is not linear with high probability, whereas if <jats:italic>p<\/jats:italic>=<jats:italic>N<\/jats:italic><jats:sup>\u22121\/2+\u03b5<\/jats:sup> for any \u03b5&gt;0 then <jats:italic>A<\/jats:italic> is linear with high probability.<\/jats:p>","DOI":"10.1017\/s096354831300014x","type":"journal-article","created":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T05:33:45Z","timestamp":1370928825000},"page":"592-611","source":"Crossref","is-referenced-by-count":1,"title":["Freiman Homomorphisms of Random Subsets of"],"prefix":"10.1017","volume":"22","author":[{"given":"GONZALO FIZ","family":"PONTIVEROS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,6,11]]},"reference":[{"key":"S096354831300014X_ref7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.4064\/aa-75-2-133-163","article-title":"Arithmetic progressions of length three in subsets of a random set.","volume":"75","author":"Kohayakawa","year":"1996","journal-title":"Acta Arithmetica"},{"key":"S096354831300014X_ref3","unstructured":"Balogh J. , Morris R. and Samotij W. (2012) Independent sets in hypergraphs. arXiv:1204.6530v1."},{"key":"S096354831300014X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S096354831300014X_ref13","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie.","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S096354831300014X_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070014"},{"key":"S096354831300014X_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01876039"},{"key":"S096354831300014X_ref9","unstructured":"Saxton D. and Thomason A. (2012) Hypergraph containers. arXiv:1204.6595v1."},{"key":"S096354831300014X_ref11","doi-asserted-by":"crossref","first-page":"199","DOI":"10.4064\/aa-27-1-199-245","article-title":"On sets of integers containing no k elements in arithmetic progression.","volume":"27","author":"Szemer\u00e9di","year":"1975","journal-title":"Acta Arithmetica"},{"key":"S096354831300014X_ref5","volume-title":"Translations of Mathematical Monographs","author":"Freiman","year":"1973"},{"key":"S096354831300014X_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140511"},{"key":"S096354831300014X_ref4","unstructured":"Conlon D. and Gowers W. T. (2010) Combinatorial theorems in sparse random sets. arXiv:1011.4310v1."},{"key":"S096354831300014X_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149"},{"key":"S096354831300014X_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10032"},{"key":"S096354831300014X_ref10","unstructured":"Schacht M. (2009) Extremal results for random discrete structures. Submitted."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831300014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T17:15:09Z","timestamp":1556039709000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831300014X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,11]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S096354831300014X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831300014x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,11]]}}}