Loading Events

« All Events

  • This event has passed.

Cheolwon Heo (허철원), Representations of even-cycle matroids

Tuesday, August 31, 2021 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


Cheolwon Heo (허철원)
Applied Algebra and Optimization Research Center (AORC), Sungkyunkwan University

A signed graph is a pair $(G,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. A cycle $C$ of $G$ is a subset of edges of $G$ such that every vertex of the subgraph of $G$ induced by $C$ has an even degree. We say that $C$ is even in $(G,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\Sigma)$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G,\Sigma)$. For even-cycle matroids, two fundamental questions arise:
(1) what is the relationship between two signed graphs representing the same even-cycle matroids?
(2) how many signed graphs can an even-cycle matroid have?
For (a), we characterize two signed graphs $(G_1,\Sigma_1)$ and $(G_2,\Sigma_2)$ where $G_1$ and $G_2$ are $4$-connected that represent the same even-cycle matroids.
For (b), we introduce pinch-graphic matroids, which can generate exponentially many representations even when the matroid is $3$-connected. An even-cycle matroid is a pinch-graphic matroid if there exists a signed graph with a pair of vertices such that every odd cycle intersects with at least one of them. We prove that there exists a constant $c$ such that if a matroid is even-cycle matroid that is not pinch-graphic, then the number of representations is bounded by $c$. This is joint work with Bertrand Guenin and Irene Pivotto.


Tuesday, August 31, 2021
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


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.