Source author record

N. Alon

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.PR

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Large cliques and independent sets all over the place

We study the following question raised by Erdős and Hajnal in the early 90's. Over all $n$ -vertex graphs $G$ what is the smallest possible value of $m$ for which any $m$ vertices of $G$ contain both a clique and an independent set of size $\log n$ ? We construct examples showing that $m$ is at most $2^{2^{(\log\log n)^{1/2+o(1)}}}$ obtaining a twofold sub-polynomial improvement over the upper bound of about $\sqrt{n}$ coming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of size $\log n$ in any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness.

preprint2020arXiv

List Ramsey numbers

We introduce the list colouring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For $\ell$ -uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well-known that the Ramsey number is super-exponential for uniformity at least $3$ . This is in great contrast to the graph case where we cannot even decide the question of equality for cliques.

preprint2010arXiv

Increasing the chromatic number of a random graph

What is the minimum number of edges that have to be added to the random graph $G=G_{n,0.5}$ in order to increase its chromatic number $χ=χ(G)$ by one percent ? One possibility is to add all missing edges on a set of $1.01 χ$ vertices, thus creating a clique of chromatic number $1.01 χ$ . This requires, with high probability, the addition of $Ω(n^2/\log^2 n)$ edges. We show that this is tight up to a constant factor, consider the question for more general random graphs $G_{n,p}$ with $p=p(n)$ , and study a local version of the question as well. The question is motivated by the study of the resilience of graph properties, initiated by the second author and Vu, and improves one of their results.

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.