Miklós Simonovits
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Miklós Simonovits has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Zoltán Füredi
Rényi Institute of Mathematics of the Hungarian Academy of Sciences Budapest, PO Box 127, Hungary-1364 and Department of Mathematics, University of Illinois at Urbana-Champaign Urbana, IL61801, USA
4 shared publications - Diana Piguet
School of Mathematics University of Birmingham Edgbaston B15 2TT Birmingham UK
3 shared publications - Jan Hladký
Institute of Computer Science Czech Academy of Sciences Prague Czechia
3 shared publications - Maya Stein
University of Chile
3 shared publications - Tomasz Łuczak
Faculty of Mathematics and Computer Science Adam Mickiewicz University Poznań Poland
3 shared publications Endre Szemerédi
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
2 shared publications
Latest Publications
- Open Access
- 22 April 2025
- Published by Akademiai Kiado Zrt. in Magyar Tudomány
- Vol. 186 (4) , 641-654
Nagy matematikusaink hatása a magyar matematika elismertségére
A magyar matematikai kutatások folyamatosan világszínvonalúak a 19. század vége óta. Ebben a két legfontosabb tényező valószínűleg a tehetséggondozás és a nemzetközi beágyazottság. Ezen állításunkat néhány kiemelkedő matematikusunk, elsősorban Erdős Pál (1913–1996) munkásságán keresztül illusztráljuk.
- 22 April 2025
- Published by Akademiai Kiado Zrt. in Magyar Tudomány
- Vol. 186 (4) , 641-654
Open AccessNagy matematikusaink hatása a magyar matematika elismertségére
A magyar matematikai kutatások folyamatosan világszínvonalúak a 19. század vége óta. Ebben a két legfontosabb tényező valószínűleg a tehetséggondozás és a nemzetközi beágyazottság. Ezen állításunkat néhány kiemelkedő matematikusunk, elsősorban Erdős Pál (1913–1996) munkásságán keresztül illusztráljuk.
- Open Access
Embedding graphs into larger graphs: results, methods, and problems
Extremal Graph Theory is a very deep and wide area of modern combinatorics. It is very fast developing, and in this long but relatively short survey we select some of those results which either we feel very important in this field or which are new breakthrough results, or which --- for some other reasons --- are very close to us. Some results discussed here got stronger emphasis, since they are connected to Lov\'asz (and sometimes to us).
Open AccessEmbedding graphs into larger graphs: results, methods, and problems
Extremal Graph Theory is a very deep and wide area of modern combinatorics. It is very fast developing, and in this long but relatively short survey we select some of those results which either we feel very important in this field or which are new breakthrough results, or which --- for some other reasons --- are very close to us. Some results discussed here got stronger emphasis, since they are connected to Lov\'asz (and sometimes to us).
- 1 January 2019
- Published by Springer Nature
- p. 445-592
Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- 1 January 2019
- Published by Springer Nature
- p. 445-592
Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Open Access
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.
Open AccessThe 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.
- Open Access
The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs
Loebl, Koml\'os and S\'os conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemer\'edi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050].Open AccessThe approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs
Loebl, Koml\'os and S\'os conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemer\'edi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050]. - Open Access
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\'os 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\'an 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\'as-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\'edi'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.Open AccessPhase 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\'os 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\'an 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\'as-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\'edi'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. - Open Access
- 1 January 2015
- Published by American Institute of Mathematical Sciences (AIMS) in Electronic Research Announcements in Mathematical Sciences
- Vol. 22, 1-11
The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
Loebl, Komlós and Sós conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemerédi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050].- 1 January 2015
- Published by American Institute of Mathematical Sciences (AIMS) in Electronic Research Announcements in Mathematical Sciences
- Vol. 22, 1-11
Open AccessThe approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
Loebl, Komlós and Sós conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemerédi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050]. - 16 January 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 69 (2) , 169-175
On the multi‐colored Ramsey numbers of cycles
For a graph L and an integer k≥2, Rk(L) denotes the smallest integer N for which for any edge‐coloring of the complete graph KN by k colors there exists a color i for which the corresponding color class contains L as a subgraph.Bondy and Erdos conjectured that, for an odd cycle Cn on n vertices, equation image They proved the case when k = 2 and also provided an upper bound Rk(Cn)≤(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≥4, equation image When n is even, Sun Yongqi, Yang Yuansheng, Xu Feng, and Li Bingxi gave a construction, showing that Rk(Cn)≥(k−1)n−2k+ 4. Here we prove that if n is even, then equation image © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 169‐175, 2012
- 16 January 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 69 (2) , 169-175
On the multi‐colored Ramsey numbers of cycles
For a graph L and an integer k≥2, Rk(L) denotes the smallest integer N for which for any edge‐coloring of the complete graph KN by k colors there exists a color i for which the corresponding color class contains L as a subgraph.Bondy and Erdos conjectured that, for an odd cycle Cn on n vertices, equation image They proved the case when k = 2 and also provided an upper bound Rk(Cn)≤(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≥4, equation image When n is even, Sun Yongqi, Yang Yuansheng, Xu Feng, and Li Bingxi gave a construction, showing that Rk(Cn)≥(k−1)n−2k+ 4. Here we prove that if n is even, then equation image © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 169‐175, 2012
- Open Access
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\H{o}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$.}$$Open AccessOn 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\H{o}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$.}$$ - 1 September 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 18 (5) , 691-705
A Combinatorial Distinction Between Unit Circles and Straight Lines: How Many Coincidences Can they Have?
We give a very general sufficient condition for a one-parameter family of curves not to have n members with ‘too many’ (i.e., a near-quadratic number of) triple points of intersections. As a special case, a combinatorial distinction between straight lines and unit circles will be shown. (Actually, this is more than just a simple application; originally this motivated our results.)
- 1 September 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 18 (5) , 691-705
A Combinatorial Distinction Between Unit Circles and Straight Lines: How Many Coincidences Can they Have?
We give a very general sufficient condition for a one-parameter family of curves not to have n members with ‘too many’ (i.e., a near-quadratic number of) triple points of intersections. As a special case, a combinatorial distinction between straight lines and unit circles will be shown. (Actually, this is more than just a simple application; originally this motivated our results.)