Researcher profile

Miklós Simonovits

Miklós Simonovits contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO

Trust snapshot

Quick read

Trust 19 - Baseline

5works

0followers

1topics

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.

preprint2015arXiv

Phase transitions in the Ramsey-Turán theory

Let $f(n)$ be a function and $L$ be a graph. Denote by $RT(n,L,f(n))$ the maximum number of edges of an $L$-free graph on $n$ vertices with independence number less than $f(n)$. Erd\H os and Sós asked if $RT\left(n, K_5, c\sqrt{n}\right) = o(n^2)$ for some constant $c$. We answer this question by proving the stronger $RT\left(n, K_5, o\left(\sqrt{n\log n}\right)\right) = o(n^2)$. It is known that $RT \left(n, K_5, c \sqrt{n\log n} \right) = n^2/4+o(n^2)$ for $c>1$, so one can say that $K_5$ has a Ramsey-Turán phase transition at $c\sqrt{n\log n}$. We extend this result to several other $K_s$'s and functions $f(n)$, determining many more phase transitions. We shall formulate several open problems, in particular, whether variants of the Bollobás-Erd\H os graph exist to give good lower bounds on $RT\left(n, K_s, f(n)\right)$ for various pairs of $s$ and $f(n)$. Among others, we use Szemerédi's Regularity Lemma and the Hypergraph Dependent Random Choice Lemma. We also present a short proof of the fact that $K_s$-free graphs with small independence number are sparse.

preprint2015arXiv

The approximate Loebl-Komlós-Sós Conjecture

We prove the following version of the Loebl-Komlos-Sos Conjecture: For every alpha>0 there exists a number M such that for every k>M every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: we decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. However, the decomposition given by the Regularity Lemma is not of help when G is sparse. To surmount this shortcoming we use a more general decomposition technique: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and two other objects each exhibiting certain expansion properties.

preprint2014arXiv

On $3$-uniform hypergraphs without linear cycles

We explore properties of $3$-uniform hypergraphs $H$ without linear cycles. Our main results are that these hypergraphs must contain a vertex of strong degree at most two and must have independent sets of size at least ${2|V(H)|\over 5}$.

preprint2013arXiv

The history of degenerate (bipartite) extremal graph problems

This paper is a survey on Extremal Graph Theory, primarily focusing on the case when one of the excluded graphs is bipartite. On one hand we give an introduction to this field and also describe many important results, methods, problems, and constructions.

preprint2010arXiv

On the Multi-coloured Ramsey Numbers of Cycles

For a graph $L$ and an integer $k\geq 2$, $R_k(L)$ denotes the smallest integer $N$ for which for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L$ as a subgraph. Bondy and Erdős conjectured that for an odd cycle $C_n$ on $n$ vertices, $$R_k(C_n) = 2^{k-1}(n-1)+1 \text{for $n>3$.}$$ They proved the case when $k=2$ and also provided an upper bound $R_k(C_n)\leq (k+2)!n$. Recently, this conjecture has been verified for $k=3$ if $n$ is large. In this note, we prove that for every integer $k\geq 4$, $$R_k(C_n)\leq k2^kn+o(n), \text{as $n\to\infty$.}$$ When $n$ is even, Yongqi, Yuansheng, Feng, and Bingxi gave a construction, showing that $R_k(C_n)\geq (k-1)n-2k+4.$ Here we prove that if $n$ is even, then $$R_k(C_n)\leq kn+o(n), \text{as $n\to\infty$.}$$