Jie Ma (马杰), Non-repeated cycle lengths and Sidon sequences
We prove a conjecture of Boros, Caro, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of …
10 events found.
Virtual Discrete Math Colloquium
Events
-
-
Zoom ID: 869 4632 6610 (ibsdimag)
-
David Wood, Tree densities of sparse graph classes
Zoom ID: 869 4632 6610 (ibsdimag)This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a …
-
-
Yixin Cao (操宜新), Recognizing (unit) interval graphs by zigzag graph searches
Room B232 IBS (기초과학연구원)Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm …
-
Édouard Bonnet, Twin-width and ordered binary structures
Zoom ID: 869 4632 6610 (ibsdimag)The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of …
-
-
Sophie Spirkl, Pure pairs in ordered graphs
Zoom ID: 869 4632 6610 (ibsdimag)A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or …
-
Michał Pilipczuk, Structural properties of powers of sparse graphs
Zoom ID: 869 4632 6610 (ibsdimag)For a graph G and an integer d, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent …
-
István Tomon, Ramsey properties of semilinear graphs
Zoom ID: 869 4632 6610 (ibsdimag)A graph $G$ is semilinear of bounded complexity if the vertices of $G$ are elements of $\mathbb{R}^{d}$, and the edges of $G$ are defined by the sign patterns of $t$ …
-
Reinhard Diestel, Tangles of set separations: a novel clustering method and type recognition in machine learning
Zoom ID: 869 4632 6610 (ibsdimag)Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover, relate, and structure …
-
-
Raul Lopes, Adapting the Directed Grid Theorem into an FPT Algorithm
Zoom ID: 869 4632 6610 (ibsdimag)The Grid Theorem of Robertson and Seymour is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for …
-
Johannes Carmesin, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings
Zoom ID: 869 4632 6610 (ibsdimag)Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, …