Source author record

Chaim Even-Zohar

Chaim Even-Zohar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

What is connected

3works

2topics

1close collaborators

Actions

Connect this record

Open graph Browse works

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.

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.