Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most …
10 events found.
Virtual Discrete Math Colloquium
Events
-
-
Zoom ID: 869 4632 6610 (ibsdimag)
-
Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture
Zoom ID: 869 4632 6610 (ibsdimag)A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic …
-
-
Ron Aharoni, Colorful KKM and multiple cakes division
Zoom ID: 869 4632 6610 (ibsdimag)In the "cake partition" problem n players have each a list of preferred parts for any partition of the interval ("cake") into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild …
-
Jie Ma (马杰), Non-repeated cycle lengths and Sidon sequences
Zoom ID: 869 4632 6610 (ibsdimag)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 …
-
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$ …