Minki Kim (김민기), Rainbow paths and rainbow matchings
Room B232 IBS (기초과학연구원)We prove that if
10 events found.
Seminars and Colloquiums
Kevin Hendrey, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Room B232 IBS (기초과학연구원)Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing …
Debsoumya Chakraborti, Some classical problems in graph saturation
Room B232 IBS (기초과학연구원)Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph
Se-Young Yun (윤세영), Regret in Online Recommendation Systems
Room B232 IBS (기초과학연구원)We propose a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a population of m users, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly, an item …
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 is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for …
Hong Liu (刘鸿), Nested cycles with no geometric crossing
Room B232 IBS (기초과학연구원)In 1975, Erdős asked the following question: what is the smallest function
É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 its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with …
Casey Tompkins, 3-uniform hypergraphs avoiding a cycle of length four
Room B232 IBS (기초과학연구원)We show that that the maximum number of of edges in a
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 none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture. In …
Rutger Campbell, Matroid orientability and representability
Room B232 IBS (기초과학연구원)In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.