Loading Events

« All Events

:

Donggyu Kim (๊น€๋™๊ทœ), ๐˜-graphic delta-matroids and their applications

October 26 Tuesday @ 4:30 PM - 5:30 PM KST

Room B232, IBS (๊ธฐ์ดˆ๊ณผํ•™์—ฐ๊ตฌ์›)

Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$, which generalizes a graphic delta-matroid.

For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid, which we call a $\Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$.

This is joint work with Duksang Lee and Sang-il Oum.

Details

Date:
October 26 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (๊ธฐ์ดˆ๊ณผํ•™์—ฐ๊ตฌ์›)

Organizer

Sang-il Oum (์—„์ƒ์ผ)
View Organizer Website
IBS ์ด์‚ฐ์ˆ˜ํ•™๊ทธ๋ฃน Discrete Mathematics Group
๊ธฐ์ดˆ๊ณผํ•™์—ฐ๊ตฌ์› ์ˆ˜๋ฆฌ๋ฐ๊ณ„์‚ฐ๊ณผํ•™์—ฐ๊ตฌ๋‹จ ์ด์‚ฐ์ˆ˜ํ•™๊ทธ๋ฃน
๋Œ€์ „ ์œ ์„ฑ๊ตฌ ์—‘์Šคํฌ๋กœ 55 (์šฐ) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.