Source author record

Chaim Even-Zohar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

3works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A Note on the Inducibility of 4-vertex Graphs

There is much recent interest in understanding the density at which constant size graphs can appear in a very large graph. Specifically, the inducibility of a graph H is its extremal density, as an induced subgraph of G, where |G| -> infinity. Already for 4-vertex graphs many questions are still open. Thus, the inducibility of the 4-path was addressed in a construction of Exoo (1986), but remains unknown. Refuting a conjecture of Erdos, Thomason (1997) constructed graphs with a small density of both 4-cliques and 4-anticliques. In this note, we merge these two approaches and construct better graphs for both problems.

preprint2014arXiv

Triply Existentially Complete Triangle-Free Graphs

A triangle-free graph G is called k-existentially complete if for every induced k-vertex subgraph H of G, every extension of H to a (k+1)-vertex triangle-free graph can be realized by adding another vertex of G to H. Cherlin asked whether k-existentially complete triangle-free graphs exist for every k. Here we present known and new constructions of 3-existentially complete triangle-free graphs.

preprint2012arXiv

On Sums of Generating Sets in (Z_2)^n

Let A and B be two affinely generating sets of (Z_2)^n. As usual, we denote their Minkowski sum by A+B. How small can A+B be, given the cardinalities of A and B? We give a tight answer to this question. Our bound is attained when both A and B are unions of cosets of a certain subgroup of (Z_2)^n. These cosets are arranged as Hamming balls, the smaller of which has radius 1. By similar methods, we re-prove the Freiman-Ruzsa theorem in (Z_2)^n, with an optimal upper bound. Denote by F(K) the maximal spanning constant |<A>|/|A|, over all subsets A of (Z_2)^n with doubling constant |A+A|/|A| < K. We explicitly calculate F(K), and in particular show that 4^K / 4K < F(K) (1+o(1)) < 4^K / 2K. This improves the estimate F(K) = poly(K) 4^K, found recently by Green and Tao and by Konyagin.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.