| Texto completo | |
| Autor(es): |
Hladky, Jan
[1]
;
Piguet, Diana
[2]
;
Simonovits, Miklos
[3]
;
Stein, Maya
[4]
;
Szemeredi, Endre
[5]
Número total de Autores: 5
|
| Afiliação do(s) autor(es): | [1] Acad Sci Czech Republic, Inst Math, Prague 11000 - Czech Republic
[2] Acad Sci Czech Republic, Inst Comp Sci, Prague 18207 - Czech Republic
[3] Renyi Inst, Budapest - Hungary
[4] Univ Chile, Ctr Modelamiento Matemat, Santiago Ctr, RM - Chile
[5] Rutgers State Univ, Dept Math, Piscataway, NJ 08854 - USA
Número total de Afiliações: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Electronic Research Announcements in Mathematical Sciences; v. 22, p. 1-11, 2015. |
| Citações Web of Science: | 5 |
| Resumo | |
Loebl, Komlos and Sos 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 Szemeredi'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]. (AU) | |
| Processo FAPESP: | 08/50338-0 - Grafos infinitos e Teoria Geométrica de grupos |
| Beneficiário: | Maya Jakobine Stein |
| Modalidade de apoio: | Bolsas no Exterior - Pesquisa |