�� <!DOCTYPE html> <html> <head> <style type="text/css"> body { font-family:Verdana; background-color:#F5F5F5; } div.horizontal { } div.horizontal ul { list-style-type:none; margin:0; padding:0; border-width:0px; } div.horizontal li { float:left; width:14.28%; } div.horizontal a { display:block; } div.horizontal a:link,div.horizontal a:visited { font-weight:bold; color:#111111; background-color:#FFFFFF; text-align:center; padding-bottom:19px; padding-top:19px; text-decoration:none; width:100%; } div.horizontal a:hover,div.horizontal a:active { background-color:#FFD700; } div.initbox { display:block; font-weight:bold; font-size:26px; color:#FFFFFF; background-color:#1E90FF; text-align:center; padding-bottom:10px; padding-top:20px; text-decoration:none; } #thispage { background-color:#FFD700; } </style> <title>Combinatorics</title> <script type="text/javascript" async src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML"> </script> </head> <body> <div class="initbox">Combinatorial group</div> <div class="horizontal"><ul> <li><a href="index.html" >Main page</a></li> <li><a href="people.html">People</a></li> <li><a href="seminar.html" id="thispage">Seminar </a></li> <li><a href="events.html">Events</a></li> <li><a href="students.html">Openings</a></li> <li><a href="outputs.html">Outputs</a></li> <li><a href="fundings.html">Funding</a></li> </ul> </div> <!-- Math code: <img src="http://latex.codecogs.com/gif.latex? THE CODE " border="0"/> --> <hr> <h2>We are shocked by the aggression happening to Ukraine. As citizens we try to help her people with our private means. As professional mathematicians, we welcome suggestions that might help our fellow Ukrainian colleagues (students or researchers) in any way. Some funds are available to this end (<a href="http://uivty.cs.cas.cz/ExtrA/students.html">here</a>). Do not hesitate to contact us!</h2> <hr> <h2>Programme</h2> <p><b> Thursday 8.9.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419 (and on <a href="http://cesnet.zoom.us/my/sileikis">ZOOM</a>), <a href="https://sites.google.com/monash.edu/nkamcev/home">Nina Kam&ccaron;ev</a> (University of Zagreb): Canonical colourings in random graphs </b></p> <p><u>Abstract</u>: R&ouml;dl and Ruci&#324;ski have extended Ramsey&rsquo;s Theorem to random graphs, showing that there is a constant C such that with high probability, any two-colouring of the edges of G(n, p) with edge probability p = Cn^{&minus;2/(t+1)} contains a monochromatic copy of K_t (the complete t-vertex graph). We investigate how this statement extends to arbitrary colourings of G(n, p). Namely, when no assumptions are made on the edge colouring, one can only hope to find one of the four canonical colourings of K_t, as in the well-known canonical version of Ramsey&rsquo;s Theorem due to Erd&#337;s and Rado. We show that indeed, any colouring of G(n,p) with p = Cn^{&minus;2/(t+1)} contains a canonically coloured copy of K_t. A crucial tool in the proof is the transference principle due to Conlon and Gowers. <br> Joint work with Mathias Schacht. </p> <h2>Past Seminars</h2> <p><b> Monday 27.6.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419 (and on <a href="http://cesnet.zoom.us/my/sileikis">ZOOM</a>), Camila Z&aacute;rate (University of Chile): Antidirected trees in oriented graphs of large semidegree</b></p> <p><u>Abstract</u>: Using the Diregularity Lemma, we prove that a sufficiently large oriented graph with minimum semidegree at least (1+p)k/2 contains a copy of every balanced antidirected tree of k edges and bounded maximum degree.<br> This is a thesis work under the supervision of Prof. Maya Stein.</p> <p><b> Monday 23.5.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419 (and on <a href="http://cesnet.zoom.us/my/sileikis">ZOOM</a>), <a href="http://sites.google.com/view/alberto-espuny-diaz/">Alberto Espuny D&iacute;az</a> (TU Ilmenau): Hamiltonicity of random subgraphs of the hypercube</b></p> <p><u>Abstract</u>: Finding thresholds for different monotone properties is one of the main goals in random graph theory, but these are easier to determine in some models of random graphs than others. In the case of (binomial) random subgraphs of the hypercube, a longstanding conjecture stated that the threshold for Hamiltonicity should be 1/2. We have recently confirmed this conjecture and obtained several generalisations. In this talk, I will present our results and describe the main ingredients of their proofs. </p> <p> This is joint work with Padraig Condon, Ant&oacute;nio Gir&atilde;o, Daniela K&uuml;hn and Deryk Osthus. </p> <p><b> Monday 11.4.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 318 (and on <a href="http://cesnet.zoom.us/my/sileikis">ZOOM</a>), <a href="http://www.math.tugraz.at/~cooley/">Oliver Cooley</a> (Graz University of Technology): Paths and cycles in random hypergraphs</b></p> <p><u>Abstract</u>: j-tight paths and cycles, in which consecutive edges intersect in precisely j vertices, are a staple of extremal hypergraph theory, but have seen relatively little attention in the random setting. We present an overview of some recent results concerning the length of the longest j-tight path or cycle in a binomial k-uniform hypergraph. These include phase transition results, analysis via core-type structures, and the sprinkling method. Some arguments are obvious generalisations of known graph proofs, while others require significant additional work. </p> <p> Parts of this talk are based on joint work with Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicol&aacute;s Sanhueza-Matamala and Julian Zalla. </p> <p><b> Monday 21.3.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419, <a href="http://pedrocaraujo.github.io">Pedro Ara&uacute;jo</a> (ICS CAS): Tight Hamiltonian cycles in uniformly dense hypergraphs</b></p> <p><u>Abstract</u>: We discuss several notions of quasirandomness in hypergraphs and their interplay with tight Hamiltonicity.</p> <p>We show that if an n-vertex 3-uniform hypergraph H=(V,E) has the property that for any set of vertices X and for any collection P of pairs of vertices, the number of hyperedges composed by a pair belonging to P and one vertex from X is at least (1/4+o(1))|X||P| - o(|V|^3) and H has minimum vertex degree at least \Omega(|V|^2), then H contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context.</p> <p>We explore possible generalizations for higher uniformities.</p> <p>This is joint work with Sim&oacute;n Piga and Mathias Schacht.</p> <p><b> Monday 14.3.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 262, <a href="http://honza.ucw.cz/">Jan Volec</a> (Czech Technical University): On Brandt conjecture on the minimum eigenvalue of regular triangle-free graph</b></p> <p><u>Abstract</u>: Motivated by two well-known conjectures of Erd&odblac;s on triangle-free graphs, Brandt asked in 1994 whether the smallest eigenvalue of an n-vertex d-regular triangle-free graph is at most 4n/25 - d. In this talk, we confirm the conjecture of Brandt. This is a joint work with Sergey Norin.</p> <p><b> Monday 28.2.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, <a style="color:red;"> room 262 </a> </b> (next to the office of the speaker)<b>, <a>Diana Piguet</a> (ICS CAS): Perfect packing of degenerate graphs</b></p> <p><u>Abstract</u>: A family of graphs packs into a host graph if there are edge-disjoint copies of every element of the family in the host graph. I shall talk about perfectly packing degenerate graphs of sublinear maximum degree into complete graphs. This work has been motivated by two beautiful tree-packing conjectures &mdash; one of Ringel from 1963 and one of Gy&aacute;rf&aacute;s from 1976. This is joint work with Peter Allen, Julia B&ouml;ttcher, Dennis Clemens, Jan Hladk&yacute;, and Anusch Taraz.</p> <p><b> Monday 14.2.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419, <a>Eng Keat Hng</a> (ICS CAS): Minimum degree conditions for powers of cycles and paths</b></p> <p><u>Abstract</u>: We study minimum degree conditions under which a graph G contains kth powers of paths and cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of $G$ is large. This extends a result of Allen, B�ttcher and Hladk� [J. Lond. Math. Soc. (2) 84(2) (2011), 269--302] concerning the containment of squares of paths and squares of cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative. </p> <p><b>Monday 7.2.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 419, <a href="https://kam.mff.cuni.cz/~tyomkyn/">Mykhaylo Tyomkyn</a> (Charles University): Limiting constants for weak saturation of hypergraphs</b></p> <p><u>Abstract</u>: For two r-uniform hypergraphs G and H we say that G is weakly H-saturated if the missing edges in G can be filled one by one, creating a new copy of H at every step. The quantity wsat(n,H) measures the smallest size of a weakly H-saturated r-graph of order n. For r=2 a short argument due to Alon (1985) shows that for any graph H, wsat(n,H)/n tends to a limit as n increases. Tuza conjectured in 1992 that for arbitrary r the quantity wsat(n,H)/n^{r-1} similarly has a limit c(H). I will present a recent proof of Tuza's conjecture.</p> <p>Joint work with Asaf Shapira (Tel Aviv University).</p> <p><b>Wednesday 12.1.2022 at 10:00 <a href="http://www.ustavinformatiky.cz/">ICS</a>, room 318, <a href="https://homepages.warwick.ac.uk/staff/Jan.Grebik/">Jan Greb&iacute;k</a> (Warwick): Local problems on bounded degree graphs</b></p> <table width="100%" border="0"> <tr> <td width="25%" height="220" align="center"> <img src="seminar-pictures/Grebik2022.jpg" width="300" class="fltrt"/> </td> <td width="75%"><p><strong></strong></p> <p><u>Abstract</u>: I will discuss some recent progress on connections between distributed computing and descriptive combinatorics. The connection is phrased in the language of local problems, i.e., coloring problems where a correctness of a given candidate coloring can be checked locally. In both fields, the goal is to understand how difficult is to produce a coloring that solves a given local problem. I will focus on the case of oriented paths, however, if time permits we might discuss other classes of graphs. This is joint work Vasek Rozhon.</p> </td> </tr> </table> <hr> <h2><a href="seminar2021.html">seminars in 2021</a></h2> <h2><a href="seminar2020.html">seminars in 2020</a></h2> <h2><a href="seminar2019.html">seminars in 2019</a></h2> <h2><a href="seminar2018.html">seminars in 2018</a></h2> <h2><a href="seminar2017.html">seminars in 2017</a></h2> <h2><a href="seminar2016.html">seminars in 2016</a></h2> </BODY> </HTML>