{"id":1484,"date":"2022-08-14T22:57:43","date_gmt":"2022-08-15T01:57:43","guid":{"rendered":"https:\/\/www.ime.usp.br\/~tcco\/?page_id=1484"},"modified":"2024-06-05T08:16:54","modified_gmt":"2024-06-05T11:16:54","slug":"seminarios-tcco","status":"publish","type":"page","link":"https:\/\/www.ime.usp.br\/~tcco\/seminarios-tcco\/","title":{"rendered":"Semin\u00e1rios TCCO"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">2024<\/h2>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-constrained wp-block-group-is-layout-constrained\">\n<ul class=\"wp-block-list\">\n<li>Joseph Hyde (University of Victoria) <br>7\/6 (sexta-feira) &#8211; 15h30 &#8211; <strong>Local:<\/strong> Audit\u00f3rio do NUMEC<br><br><strong>T\u00edtulo<\/strong>: Thresholds for random Ramsey\u00a0problems<br><br><strong>Resumo<\/strong>: The study of Ramsey properties of the binomial random graph \\(G_{n,p}\\) was initiated in the 80s by\u00a0Frankl &amp;\u00a0R\u00f6dl\u00a0and\u00a0\u0141uczak, Ruci\u0144ski &amp;\u00a0Voigt. In this area we are often interested in establishing what function \\(f(n)\\) governs \\(G_{n,p}\\) having a particular Ramsey-like property \\(P\\) or not, i.e. when \\(p\\) is sufficiently larger than \\(f(n)\\) then \\(G_{n,p}\\) a.a.s.\u00a0has \\(P\\)\u00a0and when \\(p\\) is sufficiently smaller than \\(f(n)\\) then \\(G_{n,p}\\) a.a.s. does not have \\(P\\) (the former we call a 1-statement, the latter a 0-statement). We present recent results on this topic from two different papers. In the first, we almost completely resolve an outstanding conjecture of Kohayakawa and Kreuter on asymmetric Ramsey properties. In particular, we reduce the 0-statement\u00a0to a necessary colouring problem which we solve for almost all pairs of graphs. Joint work with Candy Bowtell and Robert Hancock. <br>In the second, we prove similar results concerning\u00a0so-called anti- and constrained-Ramsey properties. In particular, we (essentially) completely resolve the outstanding parts of the\u00a0problem of determining the threshold function for the constrained-Ramsey property, and we reduce the anti-Ramsey problem to a colouring problem which we solve\u00a0for a specific collection of graphs. Joint work with Natalie Behague, Robert Hancock, Shoham Letzter and\u00a0Natasha Morrison.<br>We finish with a number of open problems.<br><br><\/li>\n\n\n\n<li>Th\u00e9o Bor\u00e9m Fabris (USP)<br>24\/5 (sexta-feira) &#8211; 15h30 &#8211; <strong>Local:<\/strong> Audit\u00f3rio Jacy Monteiro (Bloco B)<br><br><strong>T\u00edtulo<\/strong>: Circuitos mon\u00f3tonos e o problema do clique<br><br><strong>Resumo<\/strong>: Neste semin\u00e1rio ser\u00e1 apresentada uma prova combinat\u00f3ria de uma cota inferior para o tamanho de circuitos mon\u00f3tonos que computam a fun\u00e7\u00e3o Booleana \\(\\text{Clique}_{n,3}\\). A apresenta\u00e7\u00e3o ser\u00e1 baseada na prova de Simon e Tsai (2000). A cota inferior obtida por eles \u00e9 ligeiramente melhor que um resultado obtido por Razborov (1985), mas eles n\u00e3o utilizaram explicitamente o m\u00e9todo das aproxima\u00e7\u00f5es combinado com teoremas sobre sunflowers, que s\u00e3o as t\u00e9cnicas mais usuais.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Semin\u00e1rios &#8211; Problemas de separa\u00e7\u00e3o por caminhos<\/h2>\n\n\n\n<p>Teremos alguns semin\u00e1rios sobre resultados recentes acerca do problema de separa\u00e7\u00e3o por caminhos. Ser\u00e3o apresentados os resultados descritos nos seguintes trabalhos:<br>&#8211; <a href=\"https:\/\/arxiv.org\/abs\/2301.08707\">https:\/\/arxiv.org\/abs\/2301.08707<\/a><br>&#8211; <a href=\"https:\/\/arxiv.org\/abs\/2312.14879\">https:\/\/arxiv.org\/abs\/2312.14879<\/a><br>&#8211; <a href=\"https:\/\/arxiv.org\/abs\/2403.08210\">https:\/\/arxiv.org\/abs\/2403.08210<\/a><\/p>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-constrained wp-block-group-is-layout-constrained\">\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-constrained wp-block-group-is-layout-constrained\">\n<ul class=\"wp-block-list\">\n<li>George Kontogeorgiou (University of Chile)<br>3\/5 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Jacy Monteiro (Bloco B)<br><br><strong>T\u00edtulo<\/strong>: Small weakly separating path systems for complete graphs<\/li>\n<\/ul>\n\n\n\n<p><strong>Resumo<\/strong>: Let G be a graph and let P be a set of paths of G. We say that P<br>weakly separates G if for every pair of edges of G there exists a path<br>in P that contains exactly one of them. It is a well-known problem to<br>determine the size of the smallest weakly separating path system of a<br>given graph on n vertices. Around a decade ago, Falgas-Ravry,<br>Kittipassorn, Korandi, Letzter and Narayanan conjectured an upper<br>bound of O(n) paths. This was proved last year by Bonamy, Botler,<br>Dross, Naia and Skokan, who further conjectured an upper bound of<br>(1+o(1))n paths.<\/p>\n\n\n\n<p>Some authors have considered the restriction of this problem to<br>complete graphs. It is known that a weakly separating path system for<br>a complete graph on n vertices must contain at least n-1 paths. Recently, Fernandes, Mota and Sanhueza-Matamala proved that (1+o(1))n paths suffice.<\/p>\n\n\n\n<p>In recent work with Maya Stein, we proved that every complete graph on<br>n vertices has a weakly separating path system of n+2 paths. I will<br>provide a brief view of the history of the problem and a proof sketch.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div><\/div>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Francisco Calvillo Marmaneu (Universidade Pompeu Fabra)<br>3\/5 (sexta-feira) &#8211; 15h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Jacy Monteiro (Bloco B)<br><br><strong>T\u00edtulo<\/strong>: Archeology in random graphs: root-finding methods in large growing networks<\/li>\n<\/ul>\n\n\n\n<p><strong>Resumo: <\/strong>With the ubiquitous presence of networks in many areas of science and technology, numerous new challenges have gained importance in the statistical analysis of networks. One such area, termed network archaeology (Navlakha and Kingsford, 2011), studies problems related to unveiling the past of dynamically growing networks based on present-day observations. In the models studied in this area, network vertices arrive one by one, and a new vertex attaches to one or more existing vertices by an edge according to some simple probabilistic rule (this is the case, for example, for the uniform random recursive graph, or the preferential attachment model). <\/p>\n\n\n\n<p>This presentation delves into one of the simplest problems of network archaeology: root-finding. It consists of estimating the first vertex of a randomly growing network based on observing the unlabeled network at a much later point in time. We will discuss several root-finding algorithms capable of selecting a small number of nodes\u2014regardless of the graph&#8217;s size\u2014such that the root vertex is among them with high probability.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Rafael Colares (Universit\u00e9 Clermont Auvergne)<br>22\/4 (segunda-feira) &#8211; 16h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Antonio Gilioli (Bloco A)<br><br><strong>T\u00edtulo<\/strong>: A branch-and-cut algorithm for the availability-aware VNF placement problem in virtualized networks<br><br><strong>Resumo<\/strong>: In the context of telecommunication virtualized networks, a Service Function Chain (SFC) is an origin-destination traffic demand having some specific service requirements. These requirements are expressed as an ordered set of Network Functions (NF) that must be visited along the SFCs route. Within virtualized networks, the failure of a single node where a network function is hosted causes the crash of the whole SFC. Our work addresses the problem of optimally placing Virtual Network Functions throughout a 5G network so that a given set of Service Function Chains can achieve high levels of end-to-end availability. We tackle this problem from a combinatorial perspective and propose a probabilistic approach to evaluate the real end-to-end availability of a service. This generates a non-linear character to the problem which is then linearized to derive an original integer programming formulation for it. We also introduce new families of valid inequalities reinforcing the formulation. Based on these inequalities, a branch-and-cut algorithm is proposed.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Guilherme Mota (USP)<br>19\/4 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> A249 (Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Sistemas de separa\u00e7\u00e3o por caminhos em grafos completos<br><br><strong>Resumo<\/strong>: Mostraremos que em qualquer grafo completo com \\(n\\) v\u00e9rtices h\u00e1 uma cole\u00e7\u00e3o \\(P\\) de \\((1 + o(1))n\\) caminhos que <em>separa fortemente<\/em> qualquer par \\(\\{e,f\\}\\) de arestas distintas, isto \u00e9, h\u00e1 um caminho em \\(P\\) que cont\u00e9m a aresta \\(e\\), mas n\u00e3o cont\u00e9m a aresta \\(f\\), e outro caminho em \\(P\\) que cont\u00e9m a aresta \\(f\\) mas n\u00e3o cont\u00e9m a aresta \\(e\\). Al\u00e9m disso, para certas classes de grafos \\(\\alpha n\\)-regulares com \\(n\\) v\u00e9rtices, encontramos uma cole\u00e7\u00e3o de \\( (\\sqrt{3\\alpha + 1} &#8211; 1 + o(1))n\\) caminhos que separa fortemente qualquer par de arestas. Ambos os resultados s\u00e3o os melhores poss\u00edveis a menos do termo \\(o(1)\\).<br><br>Trabalho em conjunto com Cristina Gomes Fernandes e Nicol\u00e1s Sanhueza-Matamala.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F\u00e1bio Botler (USP)<br>12\/4 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Jacy Monteiro (Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Separating the edges of a graph by a linear number of paths<br><br><strong>Resumo<\/strong>: Recently, Letzter proved that any graph of order&nbsp;\\(n\\)&nbsp;contains a collection of&nbsp;\\(O(n\\log^{\\star} n)\\)&nbsp;paths with the following property: for all distinct edges&nbsp;\\(e\\)&nbsp;and&nbsp;\\(f\\)&nbsp;there exists a path \\(\\mathcal{P}\\) in&nbsp;which contains&nbsp;\\(e\\)&nbsp;but not&nbsp;\\(f\\). We improve this upper bound to&nbsp;\\(19n\\), thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluh\u00e1r and by Falgas-Ravry, Kittipassorn, Kor\u00e1ndi, Letzter, and Narayanan. Our proof is elementary and self-contained.<br><br>Joint work with Marthe Bonamy, Fran\u00e7ois Dross, T\u00e1ssio Naia and Jozef Skokan<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Vinicius Fernandes dos Santos (UFMG)<br>13\/3 (quarta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Imre Simon (IME &#8211; CCSL)<br><br><strong>T\u00edtulo<\/strong>: Jogos, Quebra-Cabe\u00e7as e Complexidade Computacional<br><br><strong>Resumo<\/strong>: Muitos jogos e quebra-cabe\u00e7as atraem o interesse de pessoas em busca de desafios intelectuais. De certa forma, a dificuldade de uma atividade ajuda a torn\u00e1-la instigante: um quebra-cabe\u00e7a muito simples rapidamente se torna desinteressante. Frequentemente tal dificuldade pode ser formalizada, permitindo demonstrar que tais jogos tamb\u00e9m s\u00e3o dif\u00edceis, em diferentes n\u00edveis, at\u00e9 mesmo para modelos computacionais.<br>O estudo da dificuldade de jogos acompanhou os avan\u00e7os da complexidade computacional, n\u00e3o s\u00f3 utilizando as ferramentas j\u00e1 existentes para a determina\u00e7\u00e3o da dificuldade de certos jogos, mas tamb\u00e9m motivando o desenvolvimento e formaliza\u00e7\u00e3o de novas ideias e modelos.<br>Nesta palestra discutiremos jogos conhecidos e como diferentes jogos, alguns conhecidos e outros artificiais, se posicionam em diversas classes de complexidade, n\u00e3o apenas nas famosas classes P e NP, mas tamb\u00e9m em classes mais gerais, como PSPACE e EXP.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Marcelo Campos (Universidade de Cambridge)<br>8\/3 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala B03 (IME &#8211; Bloco B)<br><br><strong>T\u00edtulo<\/strong>: A new lower bound for sphere packing<br><br><strong>Resumo<\/strong>: We show there exists a packing of identical spheres in \\(\\mathbb{R}_d\\) with density at least \\[(1\u2212o(1))\\frac{d\\log d}{2d+1}\\] as \\(d\\to\\infty\\). This improves upon previous bounds for general \\(d\\) by a factor of order \\(\\log d\\) and is the first asymptotically growing improvement to Rogers&#8217; bound from 1947.<br><br>Joint work with Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">2023<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Marcelo Campos (Universidade de Cambridge)<br>15\/12 (sexta-feira) &#8211; 15h &#8211; <strong>Local:<\/strong> Audit\u00f3rio Jacy Monteiro (IME &#8211; Bloco B)<br><br><strong>T\u00edtulo<\/strong>: N\u00famero de independ\u00eancia de grafos de Cayley mais esparsos<br><br><strong>Resumo<\/strong>: Dado \\(A \\subseteq \\mathbb{Z}n\\) \\(p\\)-aleat\u00f3rio, o grafo de Cayley aleat\u00f3rio \\(\\Gamma_p\\) \u00e9 definido com tendo v\u00e9rtices \\(\\mathbb{Z}_n\\) e uma aresta entre \\(x, y \\in \\mathbb{Z}_n\\) se \\(x + y \\in A\\). Para \\(p=1\/2\\), Green e Morris mostraram que o n\u00famero de independ\u00eancia de \\(\\Gamma{1\/2}\\) \u00e9 assintoticamente igual a \\(\\alpha(G(n, 1\/2))\\), com alta probabilidade. Neste semin\u00e1rio vou mostrar que o n\u00famero de independ\u00eancia de \\(\\Gamma_p\\) se iguala ao de \\(G(n,p)\\) para \\(p \\geq (\\log n)^{-1\/80}\\). <br><br>Trabalho em conjunto com Lucas Arag\u00e3o, Gabriel Dahia e Jo\u00e3o Pedro Marciano.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Nathan Benedetto Proen\u00e7a (Universidade de Waterloo)<br>22\/09 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: The Goemans and Williamson Algorithm Extended to the Weighted Fractional Cut-Covering Problem<br><br><strong>Resumo<\/strong>: A fractional cut cover is a weighted collection of cuts in a graph covering each edge at least once. The fractional cut-covering problem is to compute, given an input graph, the smallest (total) weight of a fractional cut cover. We study a generalization of this problem, where one can parametrize how many times each edge must be covered. This generalization is tied to the maximum cut problem via convex duality. This relationship affords a primal-dual extension of the celebrated work of Goemans and Williamson. We develop algorithms producing not only approximately optimal fractional cut covers, but also simultaneously certifying optimality of fractional cut-covering and maximum cut instances. <br><br>This is joint work with Marcel K. de Carli Silva (USP), Cristiane Sato (UFABC), and Levent Tun\u00e7el (University of Waterloo).<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Walner Mendon\u00e7a (USP)<br>01\/09 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Ramsey-bondade em grafos densos<br><br><strong>Resumo<\/strong>: Dizemos que um grafo \\(G\\) \u00e9 Ramsey para o par de grafos \\((F,H)\\), se em toda colora\u00e7\u00e3o das arestas de \\(G\\) com as cores vermelho e azul, existe uma c\u00f3pia vermelha de \\(F\\) ou uma c\u00f3pia azul de \\(H\\). Chv\u00e1tal mostrou que o grafo completo \\(K_n\\) \u00e9 Ramsey para o par \\((K_r,P_t)\\), para \\(n \\geq (r-1)(t-1) + 1\\). Neste semin\u00e1rio, generalizaremos o teorema de Chv\u00e1tal mostrando que para qualquer grafo \\(G\\) com \\(n=(r-1)(t-1) + 1\\) v\u00e9rtices e \\(\\delta(G)\\geq n &#8211; t\/2\\), temos que \\(G\\) \u00e9 Ramsey para \\((K_r,P_t)\\). Com este resultado, iniciamos o estudo de Ramsey-bondade em grafos densos. <br><br>Trabalho em conjunto com Lucas Arag\u00e3o, Jo\u00e3o Pedro Marciano and Rob Morris (todos do IMPA).<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Jos\u00e9 D. Alvarado (USP)<br>18\/08 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: A Canonical Ramsey Theorem with List constrains&nbsp;in G(n,p)<br><br><strong>Resumo<\/strong>: Neste semin\u00e1rio estudamos uma variante em grafos aleat\u00f3rios do Teorema de Erd\u0151s-Rado (Classical Canonical Ramsey Theorem) sobre a exist\u00eancia de c\u00f3pias &#8220;can\u00f4nicas&#8221; em arestas-colora\u00e7\u00f5es arbitr\u00e1rias de grafos completos. Estimamos a fun\u00e7\u00e3o limiar para a exist\u00eancia de tais c\u00f3pias quando impomos uma restri\u00e7\u00e3o local no n\u00famero de cores utilizadas.<br><br>Esse resultado, em colabora\u00e7\u00e3o com Y. Kohayakawa, P. Morris e G. O. Mota, ser\u00e1 aplicado num trabalho subsequente (sem restri\u00e7\u00f5es locais) onde estimamos o limiar para ciclos pares.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>T\u00e1ssio Naia (USP)<br>16\/06 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Jogando &#8220;20 perguntas&#8221; sobre grafos<br><br><strong>Resumo<\/strong>: Dez anos atr\u00e1s, G.O.H. Katona prop\u00f4s o problema determinar, para cada grafo \\(G\\), qual o menor tamanho de uma cole\u00e7\u00e3o de caminhos \\(P_1,\\ldots,P_t\\) em \\(G\\) com a seguinte propriedade: para qualquer par \\(\\{g,h\\}\\) de arestas distintas de \\(G\\), algum \\(P_i\\) intersecta \\(\\{g,h\\}\\) em apenas \\(g\\) ou apenas \\(h\\). Dizemos que essa cole\u00e7\u00e3o de caminhos <em>separa<\/em> as arestas de \\(G\\). Discutiremos avan\u00e7os recentes obtidos para esse problema, confirmando conjecturas propostas por Balogh, Csaba, Martin, and Pluh\u00e1r e por Falgas-Ravry, Kittipassorn, Kor\u00e1ndi, Letzter, e Narayanan. <br><br>Este \u00e9 um trabalho feito em colabora\u00e7\u00e3o com F\u00e1bio Botler, Marthe Bonamy, Fran\u00e7ois Dross and Jozef Skokan.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li> Nicol\u00e1s Sanhueza-Matamala (Universidad de Concepci\u00f3n)<br>19\/05 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Cycle decompositions in hypergraphs<br><br><strong>Resumo<\/strong>: A cycle decomposition of a hypergraph \\(G\\) is an edge-disjoint collection of cycles which use every edge of \\(G\\). We will present recent results about cycle decompositions in dense uniform hypergraphs, and its relations with the problem of finding hypergraph Euler tours. <br><br>Based in joint work with Allan Lo and Sim\u00f3n Piga.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Cristina Gomes Fernandes (USP)<br>05\/05 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Empacotamento de \u00e1rvores balanceadas quase geradoras no \\(K_{n,n}\\)<br>(ou&#8230; minha saga com o Lema da Regularidade)<br><br><strong>Resumo<\/strong>: Em 1976, Gy\u00e1rfas conjecturou que qualquer sequ\u00eancia de \u00e1rvores \\(T_1,\\dots,T_n\\), onde \\(T_i\\) tem ordem \\(i\\), pode ser empacotada no \\(K_n\\).&nbsp; Mais recentemente, em 2013, Hollingsworth apresentou uma variante bipartida desta conjectura, que diz que qualquer sequ\u00eancia de \u00e1rvores \\(T_{1,1},\\dots,T_{n,n}\\), onde \\(T_{i,i}\\) tem \\(i\\) v\u00e9rtices em cada lado da sua biparti\u00e7\u00e3o, pode ser empacotada no \\(K_{n,n}\\).&nbsp; Tais \u00e1rvores s\u00e3o chamadas de <em>balanceadas<\/em>.&nbsp; Existem muitos resultados relacionados \u00e0 primeira conjectura, mas nem tantos sobre a segunda, mais recente.&nbsp; Neste semin\u00e1rio, daremos uma ideia da prova do seguinte resultado que obtivemos no contexto da segunda conjectura.&nbsp; Informalmente, para \\(n\\) suficientemente grande, sempre \u00e9 poss\u00edvel empacotar perto de \\(\\sqrt{n}\\) \u00e1rvores quase geradoras no \\(K_{n,n}\\).&nbsp; Formalmente, para todo \\(\\gamma &gt; 0\\), existe \\(n_0\\) tal que, para todo \\(n \\geq n_0\\), qualquer fam\u00edlia de \\(n^{\\frac12-\\gamma}\\) \u00e1rvores balanceadas em \\(2(1-\\gamma)n\\) v\u00e9rtices pode ser empacotada no \\(K_{n,n}\\).<br><br>Este \u00e9 um trabalho feito em conjunto com T\u00e1ssio Naia, Giovanne dos Santos e Maya Stein.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Yani Pehova (LSE)<br>31\/03 (sexta-feira) &#8211; 14h &#8211; <strong>Local:<\/strong> Sala A241 (IME &#8211; Bloco A)<br><br><strong>T\u00edtulo<\/strong>: Transversal factors and spanning trees<br><br><strong>Resumo<\/strong>: In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which \\(d\\) do \\(n\\)-vertex graphs with minimum degree \\(d\\) always contain a fixed subgraph \\(H\\)? We consider a collection of \\(m\\) graphs on the same set of \\(n\\) vertices whose minimum degree is at least \\(d\\), and ask which \\(d\\) guarantee the existence of a fixed (\\(m\\)-edge) subgraph \\(H\\) using exactly one edge from each&nbsp;graph in the collection. The obtained copy of \\(H\\) is called a&nbsp;<em>transversal<\/em>, or a&nbsp;<em>rainbow copy<\/em>&nbsp;if we view each graph&nbsp;as a different colour. We give asymptotically optimal minimum degree thresholds for the existence of rainbow spanning trees with maximum degree&nbsp;\\(o(n\/\\log\u2061&nbsp;n)\\)&nbsp;and perfect \\(F\\)-tilings in this setting. <br><br>This is joint work with Alp M\u00fcyesser and Richard Montgomery.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p class=\"has-medium-font-size\"><strong>2022<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Carla Negri Lintzmayer (UFABC) <\/li>\n\n\n\n<li><em>Data<\/em>: 27\/10 &#8211; 14h &#8211; <strong>LOCAL: Sala B016 (IME &#8211; Bloco B)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>T\u00edtulo: <\/strong>Arboresc\u00eancias folhudas em DAGs<\/p>\n\n\n\n<p><strong>Resumo: <\/strong>Este semin\u00e1rio resume os principais resultados que obtivemos em algoritmos de aproxima\u00e7\u00e3o para o problema de encontrar \u00e1rvores geradoras com n\u00famero m\u00e1ximo de folhas em digrafos ac\u00edclicos, uma \\(3\/2\\)-aproxima\u00e7\u00e3o e uma \\(7\/5\\)-aproxima\u00e7\u00e3o, o que envolve a rela\u00e7\u00e3o deste com outros problemas interessantes (emparelhamentos e conjuntos independentes).<br>Trabalho em conjunto com Cristina G. Fernandes.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Victor Sanches Portella (University of British Columbia)<\/li>\n\n\n\n<li><em>Data<\/em>: 21\/10 &#8211; 14h<\/li>\n<\/ul>\n\n\n\n<p><strong>T\u00edtulo: <\/strong>Quando Online Learning encontra C\u00e1lculo Estoc\u00e1stico<\/p>\n\n\n\n<p><strong>Resumo:<\/strong> Online learning (OL) \u00e9 um modelo te\u00f3rico de aprendizado de m\u00e1quina que relaxa as hip\u00f3teses t\u00edpicas feitas sobre a fonte de dados. Um dos casos mais fundamentais de OL \u00e9 o problema de predi\u00e7\u00e3o com ajuda de experts. Nele, um jogador tem que fazer uma sequ\u00eancia de predi\u00e7\u00f5es, por exemplo, predizer a cada dia se chover\u00e1 ou n\u00e3o no dia seguinte. Ao inv\u00e9s de fazer a predi\u00e7\u00e3o sem nenhuma informa\u00e7\u00e3o, o jogador tem acesso a dicas de um conjunto de experts. Em cada rodada, o jogador escolhe um dos experts, possivelmente de forma aleatorizada, cuja sugest\u00e3o ele vai seguir. Depois de cada escolha do jogador, um advers\u00e1rio decide quais experts estavam certos. Mesmo com a natureza adversarial desse modelo, existem estrat\u00e9gias que permitem o jogador de certa forma predizer t\u00e3o bem quanto o melhor dos experts. Para al\u00e9m de OL, esse problema tem aplica\u00e7\u00f5es em v\u00e1rias \u00e1reas, tais como boosting, otimiza\u00e7\u00e3o combinat\u00f3ria, privacidade, dentre outras.<\/p>\n\n\n\n<p>O problema dos experts \u00e9 um cl\u00e1ssico de OL. No entanto, ainda existem perguntas em aberto sobre ele. Por exemplo: ser\u00e1 que um jogador que sabe&nbsp;<em>de antem\u00e3o<\/em>&nbsp;o n\u00famero de predi\u00e7\u00f5es que ter\u00e1 que fazer no total \u00e9 um melhor preditor do que um que n\u00e3o tem essa mesma informa\u00e7\u00e3o? Essa pergunta nos levou a estudar uma vers\u00e3o do problema dos experts em que, ao inv\u00e9s de uma sequ\u00eancia discreta de decis\u00f5es, o jogador faz uma predi\u00e7\u00e3o&nbsp;<em>em todo instante de tempo de forma cont\u00ednua<\/em>. Nesta palestra, farei uma breve introdu\u00e7\u00e3o ao problema dos experts e algumas de suas aplica\u00e7\u00f5es. Em seguida, discutirei o modelo com tempo cont\u00ednuo, como podemos desenvolver estrat\u00e9gias para o jogador usando c\u00e1lculo estoc\u00e1stico, e como podemos em alguns casos transferir esses algoritmos e resultados de volta ao caso discreto. <\/p>\n\n\n\n<p>Parte desse trabalho foi em conjunto com Nick Harvey, Chris Liaw, e Laura Greenstreet.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Cl\u00e1udio Lucchesi (USP)<\/li>\n\n\n\n<li><em>Data<\/em>: 07\/10 &#8211; 14h<\/li>\n<\/ul>\n\n\n\n<p><strong style=\"font-size: inherit;\">T\u00edtulo<\/strong><span style=\"font-size: inherit;\">: <\/span>Grafos cobertos por emparelhamentos<\/p>\n\n\n\n<p><strong>Resumo<\/strong>: Um grafo \u00e9 coberto por emparelhamentos (gce) se \u00e9 conexo e toda aresta pertence a um emparelhamento perfeito. Os grafos c\u00fabicos 2-aresta-conexos s\u00e3o todos cobertos por emparelhamentos. Os exemplos mais ilustres de gce s\u00e3o o $K_4$, o prisma triangular e o grafo de Petersen. <\/p>\n\n\n\n<p>A origem desse estudo est\u00e1 no final do s\u00e9culo 19, com o ent\u00e3o Problemas das 4 cores. Mas recentemente tem havido muito progresso, com teoremas bonitos e conjecturas atraentes. Em particular h\u00e1 um teorema, cuja demonstra\u00e7\u00e3o, do Lov\u00e1sz, com certeza est\u00e1 no livro de Deus de Erd\u0151s.<\/p>\n\n\n\n<p>Pretendemos dar uma amostra da \u00e1rea para degusta\u00e7\u00e3o, tamb\u00e9m com apresenta\u00e7\u00e3o de alguns problemas em aberto e conjecturas interessantes.<\/p>\n\n\n\n<p>Em coautoria com U. S. R. Murty, estamos prestes a enviar para publica\u00e7\u00e3o o livro &#8220;Perfect Matchings: A Theory of Matching Covered Graphs&#8221;.<\/p>\n\n\n\n<p>Outro livro b\u00e1sico na \u00e1rea \u00e9 o livro de Lov\u00e1sz e Plummer, &#8220;Matching Theory&#8221;.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.math.ias.edu\/~lenacore\/\" target=\"_blank\">Leonardo Nagami Coregliano<\/a> (<a rel=\"noreferrer noopener\" href=\"https:\/\/www.ias.edu\/math\" target=\"_blank\">IAS Princeton)<\/a><\/li>\n\n\n\n<li><em>Data<\/em>: 25\/08 &#8211; 14h<\/li>\n<\/ul>\n\n\n\n<p><strong style=\"font-size: inherit;\">T\u00edtulo<\/strong><span style=\"font-size: inherit;\">: <\/span>O n\u00famero crom\u00e1tico abstrato<\/p>\n\n\n\n<p><strong>Resumo<\/strong>: Qual \u00e9 a densidade de um grafo que garante que ele conter\u00e1 uma c\u00f3pia de um subgrafo em particular? Ou que ele conter\u00e1 um subgrafo em uma fam\u00edlia \\(\\mathcal{F}\\) ? O c\u00e9lebre Teorema de Erd\u0151s&#8211;Stone&#8211;Simonovits caracteriza a densidade m\u00e1xima de grafos livres de c\u00f3pias de \\(\\mathcal{F}\\) em termos do m\u00ednimo dos n\u00fameros crom\u00e1ticos dos grafos em \\(\\mathcal{F}\\). Recentemente, generaliza\u00e7\u00f5es desse teorema para grafos ordenados, grafos ciclicamente ordenados, grafos com arestas ordenadas, etc. foram provadas em termos de variantes do n\u00famero crom\u00e1tico.<\/p>\n\n\n\n<p>Em um trabalho recente com A. Razborov, um resultado an\u00e1logo desse teorema foi provado no contexto de &#8220;grafos com estrutura extra arbitr\u00e1ria&#8221; (formalmente, esse contexto \u00e9 capturado por interpreta\u00e7\u00f5es abertas da teoria de grafos em uma teoria universal de primeira-ordem \\(T\\)) em termos de um <em>n\u00famero crom\u00e1tico abstrato<\/em>. Por\u00e9m, como o nome sugere, a primeira f\u00f3rmula para tal n\u00famero crom\u00e1tico abstrato \u00e9 t\u00e3o abstrata que sua computabilidade foi deixada como problema aberto.<\/p>\n\n\n\n<p>Nesta palestra, apresentarei essa generaliza\u00e7\u00e3o do teorema de Erd\u0151s&#8211;Stone&#8211;Simonovits, e uma f\u00f3rmula alternativa para o n\u00famero crom\u00e1tico abstrato que se baseia em uma vers\u00e3o partida do teorema de Ramsey. Uma consequ\u00eancia de tal f\u00f3rmula alternativa \u00e9 a computabilidade do n\u00famero crom\u00e1tico abstrato quando a teoria universal \\(T\\) subjacente \u00e9 finitamente axiomatiz\u00e1vel.<\/p>\n\n\n\n<p>Esta palestra n\u00e3o requerer\u00e1 nenhum conhecimento pr\u00e9vio.<\/p>\n\n\n","protected":false},"excerpt":{"rendered":"<p>2024 Semin\u00e1rios &#8211; Problemas de separa\u00e7\u00e3o por caminhos Teremos alguns semin\u00e1rios sobre resultados recentes acerca do problema de separa\u00e7\u00e3o por caminhos. Ser\u00e3o apresentados os resultados descritos nos seguintes trabalhos:&#8211; https:\/\/arxiv.org\/abs\/2301.08707&#8211; https:\/\/arxiv.org\/abs\/2312.14879&#8211; https:\/\/arxiv.org\/abs\/2403.08210 Resumo: Let G be a graph and let P be a set of paths of G. We say that Pweakly separates G if [&hellip;]<\/p>\n","protected":false},"author":5,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1484","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/1484"}],"collection":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/comments?post=1484"}],"version-history":[{"count":86,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/1484\/revisions"}],"predecessor-version":[{"id":2055,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/1484\/revisions\/2055"}],"wp:attachment":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/media?parent=1484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}