Missing citations

Stream: Seymour

[Martin Dvořák]

I think we miss several citations in the second paragraph of Introduction. Namely:

As for Seymour’s theorem, it not only presents a structural characterization of the class of regular matroids, but also leads to several important applications, such as polynomial algorithms for testing if a matroid is binary [1] and for testing if a matrix is totally unimodular [2]. Additionally, Seymour’s theorem can offer a structural approach for solving certain combinatorial optimization problems, for example, it leads to the characterization and efficient algorithms for the cycle polytope [3].

Can somebody provide references for the placeholders [1], [2], [3] please?

Just reply in the thread. I will make it appear in the new version.

[Cameron Rampell]

Seems like for number 2, Seymour, JCTB 28 (1980), p. 306, Introduction works. "Edmonds used it in an algorithm to recognize totally unimodular matrices (combining it with the work of Bixby and Cunningham, and Cunningham and Edmonds)."

[Martin Dvořák]

What is JCTB please? Is it any of the source we already cite?

[Cameron Rampell]

Sorry, it's the Journal of Combinatorial Theory. I found it in a PDF here: https://web.math.princeton.edu/~pds/papers/regular/paper.pdf

[Martin Dvořák]

Journal Of Combinatorial Theory

[Martin Dvořák]

Thanks!

[Cameron Rampell]

Do you think this could also work for [1], or should we find a separate citation?

[Martin Dvořák]

Somebody tell me please — I don't want to read a paper full of informal MathematiCS.

[Cameron Rampell]

Looks like [3] can be cited from https://www.sciencedirect.com/science/article/pii/S0195669881800339?via%3Dihub (file is
cycle_polytope.pdf. I'm not sure where a citation for [1] is (is it even true? Decomposition theorem, which I believe follows from Seymour, tells us if a matroid is regular. But I can't find anything related to binary matroids and Seymour).

[Martin Dvořák]

They are all binary matroids by definition. I don't know what @Ivan S. meant when he wrote it.

[Martin Dvořák]

To be more precise, the result of compositions (i.e., a matroid for which Matroid.IsGood holds) is binary by definition.
For the decomposition direction, which starts by assuming that M is regular, Matroid.IsRegular.isBinary proves that M is binary.

[Martin Dvořák]

Speaking of binary matroids, it definitely wouldn't hurt to add

lemma Matroid.IsGood.isBinary {M : Matroid α} (hM : M.IsGood) :
    ∃ X Y : Set α, ∃ A : Matrix X Y Z2, A.toMatroid = M

explicitly to the project.

[Martin Dvořák]

I'll do it: https://github.com/Ivan-Sergeyev/seymour/issues/192

[Martin Dvořák]

At the same time, I would simply omit "polynomial algorithms for testing if a matroid is binary" in the Introduction. Regardless of whether it is true or not, it is an uninteresting problem.

[Martin Dvořák]

The question is whether the plural "several applications" in the part "(...) but also leads to several important applications, such as polynomial algorithms for testing if a matrix is totally unimodular. " deserves to stay there.

[Martin Dvořák]

Perhaps this is what the paragraph should say:

"As for Seymour’s theorem, it not only presents a structural characterization of the class of regular matroids, but also leads to important applications, such as polynomial-time algorithms for testing whether a matrix is totally unimodular. Additionally, Seymour’s theorem can offer a structural approach for solving certain combinatorial optimization problems, for example, it leads to the characterization and efficient algorithms for the cycle polytope."

[Martin Dvořák]

Cameron Rampell said:

Looks like [3] can be cited from https://www.sciencedirect.com/science/article/pii/S0195669881800339?via%3Dihub

Thanks! I guess we should cite Seymour himself. It is a bit weird that no Seymour's publication is cited in the current version.

[Martin Dvořák]

Cameron Rampell said:

I'm not sure where a citation for [1]

One thing I found, in case somebody wants to characterize binary matroids where the matrix is not provided, is "noncontainment of U2,4 as a matroid minor" (discovered by Tutte, formalized by Gusakov). I don't know whether it is related to Seymour's theorem.