Researcher profile

N. Alon

N. Alon contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO math.PR

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

2topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

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.