Speaker:

Chao Xu (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• June 9, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

Let $k$ be an integer and $M$ a matroid on groundset $E$.
There is a label function $\ell:E\to [k]$ that assigns a label to all elements.

We aim to identify a base where the sum of the labels equals $b \pmod k$.
An special case would be the identification of a spanning tree with even weight.

We demonstrate that this problem is Fixed Parameter Tractable (FPT) with respect to $k$, under the assumption of a specific conjecture proposed by Schrijver and Seymour.
This conjecture is already proven for instances where $k$ is a power of a prime.
We show under the conjecture, any base is close to a base of label $b\pmod k$
for each $b$ in terms of hamming distance.
This result can be generalizable to finite abelian groups.

We also plan to discuss the optimization version of this problem.

This is joint work with Siyue Liu.