Eero Räty, Positive discrepancy, MaxCut and eigenvalues of graphs
Room B332 IBS (기초과학연구원)The positive discrepancy of a graph
10 events found.
Magnus Wahlström, Algorithmic aspects of linear delta-matroids
Room B332 IBS (기초과학연구원)Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid is a pair
Víctor Dalmau, Right-adjoints of Datalog Programs
Room B332 IBS (기초과학연구원)We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to B if and only if A maps homomorphically to Γ(B). If this is the case Λ is called the left adjoint to Γ and Γ …
Maximilian Gorsky, Towards the half-integral Erdős-Pósa property for even dicycles
Room B332 IBS (기초과학연구원)A family
Tony Huynh, Aharoni’s rainbow cycle conjecture holds up to an additive constant
Room B332 IBS (기초과학연구원)In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉. In this talk, we prove that Aharoni's conjecture holds up to an additive constant. …
Niloufar Fuladi, Cross-cap drawings and signed reversal distance
Room B332 IBS (기초과학연구원)A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. A cross-cap drawing of a graph G with g cross-caps can be used to represent an embedding of G on a …
Vadim Lozin, Graph problems and monotone classes
Room B332 IBS (기초과학연구원)Very little is known about critical properties of graphs in the hierarchy of monotone classes, i.e. classes closed under taking (not necessarily induced) subgraphs. We distinguish four important levels in this hierarchy and discuss possible new levels by focusing on the Hamiltonian cycle problem. In particular, we obtain a number of results for this problem …
Yongho Shin (신용호), Three-way online correlated selection
Room B332 IBS (기초과학연구원)Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020, JACM 2022) to break …
Jane Tan, Semi-strong colourings of hypergraphs
Room B332 IBS (기초과학연구원)A vertex colouring of a hypergraph is
Maria Chudnovsky, Anticomplete subgraphs of large treewidth
Room B332 IBS (기초과학연구원)We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth …