Teorie matroidů

Erratum to Introduction to Matroid Theory (Lecture notes) - ITI Series 2009-430

page 6, line 2 of Theorem 1.2: 'a family' -> 'the family'
page 6, line -11: instead of "I \not\subseteq C_1" it should be "C_1\not\subseteq I", I think.
page 7, last line before Proposition 1.4: 'a simple fact' -> 'the simple fact'
page 7 line 13: the dot before "which" should be a comma
line 15: "implies" should be "imply"
page 8, line 10: 'of bases of a matroids' -> 'of bases of a matroid'
line 15: 'Fox every' -> 'For every'
line 2 of the proof of Thm 1.7: add 'that' after 'holds'
page 9, line 2 of subsection 1.2: either "a" is missing before "largest", or "subset" should be plural maybe (next line) but the first solution seems to be the correct one...
page 9, line -5: maybe elsewhere too, but "obtain" should generally not be followed by "that" (read on the advices of the London Math Society...).
page 10, line 1 of the proof of Lemma 1.10: remove 'the' before 'induction' (and, maybe, add a comma after Y\X)
2 lines before Thm 1.11: 'guarantees' -> 'guarantee'
line 2 of Thm 1.11: 'a family' -> 'the family'
page 10, line 11: "subtree with rooted" -> "subtree rooted"
page 10, last line: "I_1 + x" should be "I_1 + e"
page 11, line -4: "of vector of" should be "of vectors of"
page 12, line 8: in the definition of affinely dependent, it should be that the elements a1,...,ak are not all zeros (and not, as written, that none of them should be zero)
page 13, line -1: add 'the' between 'consider' and 'sets'
page 15, line -2: i-viii should be i-vii (and maybe it should be in math mode to match the fonts with that of the list)
page 15: the last paragraph is a bit weird because you first define 'A', and then use the expression 'a non-zero matrix A', which apparently you think to be the same because you take r to be its rank. I think it should be reformulated somehow. Maybe, first you can say that it is weel known that a non-zero matrix of rank r can be transformed, by a sequence of operations i-viii, into a matrix... Then, you can say something like: Thus, if A is a representation of...
page 16, line -13: "a considered field" should be "the considered field"
page 16, line -2: remove the comma after "satisfies" maybe
page 17, line 1: "a spanning" -> "the spanning"
page 17, proposition 1.19 and proposition 1.20: "Let I be a family" -> "Let I be the family"
page 19, line 4 of section 2.1: "a family" should be "the family"
page 19, line 6 of section 2.1: same remark
page 19, line -8: (B_1 - f) + x -> x should be e
page 19, line -3: "element x" should be "element e"
page 20, line 1: remove the very first "and"
page 20, line 8: remove "of" in "all of the"
page 20, line 13: "referred as to" should be "referred to as"
page 20, line 15: "fact that matroid" -> "fact that a matroid"
page 20, line 15: the end of the sentence is awkward, for instance add "the following" after "observe"
page 21, pf of lemma 2.5: it seems more natural (and shorter) to do the computation in the other way, that is to apply 2.4 with X=C*. We then directly get r(E \ C*) = r*(C*) - |C*| + r(M) = r(M) -1. [as far as I can see, you applied 2.4 with X=E\C*].
page 22, line 3: "and their sets" should be "of their sets"
line 5: "with the ground" -> "with ground"
line 8: "contracting of a set" -> remove "of"
line 10: "We like to remark" -> We note
line 20: it seems you use two different notations for setminus, either - or \setminus. You should unify it (I guess you should keep - and + throughout (for things like (X-e)+e') and define it somewhere if needed).
line 24: at the beginning of the displayed computation, maybe start with r_{M/T}(X) = r_{M*/T}^*(X) = ... just to explicit how you apply 2.4 (costs nothing) still in the displayed computation, there's an additional "=" at the end of the one-before last line
line -2: remove "of a base"
line -1: maybe you should use ":" instead of "|" in the set, since "|" is also the restriction (deletion), it looks confusing.
page 23, Corollary 2.10: again "of a base" should be removed. Add "the" between "precisely" and "sets B'"
page 24: first line of the paragraph after the proof (starting with "Lemma 2.12 implies that...") -> add an "s" to "contraction"
line -5: "its representation" not very clear of which. Maybe reformulate by just naming the matroid (We now want to... of the dual or a minor of a matroid M from a representation of M" or something similar...)
page 25, second line of the proof: "are precisely bases" -> "are precisely the bases" add a dot at the end of the displayed matrices (after "Split now")
page 25, Figure 2.1: in the rightmost matrix, the vertical bar should be a bit more to the right (between 'e_r' and 'e_{r+1}', as in the leftmost matrix)
page 26 line -7 and line -6: add 'the' between 'removing' and 'edges', and between 'contracting' and 'edges'
page 26, line -4: remove 'the' before 'edges'
page 27, line 6: not sure, but it seems to me that you could mention Prop. 2.9 here...
line 11: maybe reformulate to avoid the confusing and not good looking "G,G^*"
pf of lemma 2.21: line 1: edge -> edges
line 2: after "Since (G*)*=G" and "and G* is connected"
line 12: add "to show" after "Euler's formula" forms -> form
page 28, line 2: add "an" between "that" and "edge-cut". Also, the def. of edge-cut is not formulated in the clearest way I think. There are examples in papers; probably something like: A set F of edges is an edge-cut if there exists a partition (A,A') of V such that F is precisely the set of edges with one end-vertex in A and the other in A'. Maybe also F should be non-empty (or the parts of the partition). So "A non-empty set F of edges is..."
line 15: "is an inclusion-wise minimal," -> remove "an"
line 21: "contained in a complement" -> "contained in the complement"
page 31, line 4: "is using an oracle" -> maybe "is to use an oracle" is nicer
line 13: "in this lecture notes" -> "in these lecture notes"
page 33, line 1: "for that" -> "for which"
line 7 of the pf of thm 3.3: I'm not sure here, but I think that "Again, but the choice of I'[...]contained in I." is not needed, and actually not true. Am I right?
line -3: "constructs a set I_1" -> "constructs the set I_1"
page 34, line 11: remove the "the" that starts the line
line -7: there is no need to minimize "r_{M_1}(E_1) + r_{M_2}(E_2)": it is not used, and you actually show it for all subsets E1,E2 such that E=E_1 U E_2 (and hence, also for those minimizing...). So it should be removed.
line -4: maybe I already said it but no "that" after "have"
line -3: I think the first \leq could be an =
line -1: likewise
Thm 3.4: add 'the' between 'are' and 'families' and then swap 'sets' and 'independent'. Finally, I would add ", respectively' ad the end of the sentence.
page 35, line 1: I don't think there's any need of the submodularity here. What you do actually is: |E'| <= |E'\cap E_1| + |E'\cap E_2| <= r(E_1) + r(E_2) by 3.2 and 3.3 and you're done!
line 6: I would reformulate as "We prove that there exists either a set E'' with |E''|>|E'| that is independent in both M_1 and M_2, or a partition..."
line 20: "Consider such a shortest path" -> "Consider a shortest such path" (you haven't talked about a "shortest path" yet, so "such a shortest path" is not ok).
line -6: "for i=k+1,...,l" is confusing: "for some i\in\{k+1,...,l}"
page 39, line -11: "equals to" -> either "equals" or "is equal to"
line -10/-9: I would rather write: "[...]exists a subset U_1\subseteq V_1 such that each edge of E_1 has an end-vertex in U_1 and |U_1|=r(E_1)". Same comment for the next sentence.
line -3: "Analogoues" -> "Analogues"
line -2: "favor" -> "flavor"
page 40, line 6: "Let E_0 be" -> "Let E be"
line 8/9: there is a small trouble here in the formulation. As far as I understand, E'\cap(E x {i}) cannot be independent "in M", as it is not a subset of E. I think what you want to write is: "...if, for each $i\in\{1,\ldots,k\}$, the set \{e\in E\,:\,(e,i)\in E'\} is independent in M"
line 11 & throughout the chapter: is [e,i] the standard notation for a pair of elements? I think (e,i) is maybe a candidate too.
line 12: it seems to me that "second coordinate" should be "first coordinate" (indeed, you partition regarding the first coordinate, and then you want at most one element from each part)
line 15: "is a set independent" -> "is independent"
line -10: "the inequality from..." maybe you want to label this inequality and then use its name...
line -7: a dot is missing at the end of the displayed inequality.
line -5: "exist" -> "exists"
page 41, line 3: I would move "by Theorem 3.4" at the end of the previous line, i.e. after "independent both in M_1 and M_2"
line 20: "the rank r_M(S)" sounds weird to me. Maybe remove "the rank" or if you prefer add "of S" after it. Same remark for "r_M(E)".
page 42, line 4: same remark as before regarding E'\cap (E x {i}).
line 7: exist -> exists
line 11: a dot is missing at the end of the displayed inequality.
line 13: exist -> exists
line 19: remove the semi-colon at the end of the displayed equation.
Theorem 4.6: I would reformulate in a more concise way and in one sentence, like: "A graph G with colored edges contains a rainbow spanning tree[...]"
page 43, The next one is maybe even less important than usual! line 5: to be consistent with what you do after, I suggest to reformulate (4.3) as: "r_{M_1}(E')+r_{M_2}(E\E') >= n-1 for all E'\subseteq E" As the '=' is not needed [it comes directly by the theorem, as every set that is independent in M_1 cannot have size more than n-1]: you show that for every E' in E, the rank of... is at least n-1. Thus, Thm 3.4 implies the existence of a set of size n-1 ind. in both M_1 and M_2. That's it. In particular, I suggest removing the sentence "As r_{M_1}(E)=n-1 and "r_M_2(\emptyset)=0".
line 9: "number of the colors" -> "number of colors"
line -1: remove the final "to" (or add "be" after if you prefer).
page 44, line 14: the sentence with "it is enough to present a polynomial-time algorithm..." is a bit unprecise: I think it should be said that the complexity of the algorithm is not exponential in k or l [like, saying "polynomial in n,m,k and l" for instance]. Otherwise it would not be sufficient (I mean, for every k, you have a polytime to test whether the clique size of a graph is at most k. There are at most n values taken by k, but yet you don't have a polytime to compute the clique-size (because the polytime for fixed k is exponential in k).
line -10: add "that" after "Observe"
line -10/-9: I think the phrasing is a bit confusing here. When you read it, it seems the reasonning is: r(F) <= |V(K)| (where I call K the subgraph spanned by F) |F| <= k * |V(K)| (because of the mad assumption) so |F| <= k * r(F) thus using an inequality in the wrong direction (I know it's not what you *mean*, but I'm pretty sure it's what one would understand when first reading this). I suggest taking one or two additional lines to do it properly (e.g. take a component C of K, say its edge-set is F'\subseteq F. If C is acyclic then |F'|=r(F'). If not then r(F')=|C| so |F'|<= k|C|= k*r(F'). Then you can sum-up on all the components (for this you can maybe start saying "Observe that it is enough to prove it for a set of edges spanning a connected subgraph of G").
page 45, line 17: exist -> exists
line -3: "to show that any two[...]" I would write "to show that for any two sets Z_1 and Z_2" and then start the displayed relation [because it's not really the sets which satisfy (4.4), rather their rank]
page 46, The one comment that delayed this email, without reason as I have still not checked it thoroughly! More importantly, I think that you should check axiom (I_3) instead of (R_3). It is more straightforward, much shorter and quite easier. I have not checked what I write below, but I'm pretty confident that something along those lines would do. Unless I missed something (which is likely), you could define a set to be independent as "A subset Z of the ground set E is independent in ... if there exists an index set I\subseteq\{1,...,m\} of size |Z| such that Z contains a transversal of ...". This is the definition you give, stated in terms of independent sets rather than rank. A better way to give it under this form is to say that Z is independent if and only if there exists an injection f of Z into {X_1,...,X_m}. Then, (I_1),(I_2) are clear, and you want to show (I_3), that is: if |Z|<|Z'| then there is e\in Z' \ Z s.t. Z_1+e is independent. Let f and f' be the corresponding injections. Take z' in Z' \ Z. If f'(z') is not in f(Z) then we are done since Z U {z'} is independent. Now, I think that one application of Hall's Theorem (in the flavor of the one suggested in parenthesis on page 46 line 5) is enough. What do you think?
page 46, line 2: I think the writing is a bit loose ("let z_i^\cap... be one of the transversals" is not too good a writing).
line -13: "are colored" -> "is colored".
line -9: for consistency, write "the color $1$" instead of "the first color".
line -6: maybe recall here that if a vertex has color $i$ then it belongs to $Z_i$.
page 47, line 1: remove "that"
line 3: add a dot at the end of the displayed inequality (4.5).
lines 9 and 11: remove "that".
line 14: add "the" before "last".
line 15: "d_y" -> "d_Y".
line 16: add a dot at the end of the displayed formula (4.8).
line -2: "the common" -> "a common".
page 51, line -13: $r(F \cap X) = |F \cap X|$ -> $r(F \cap X) = |F_X|$ and $r(F \setminus X) = |F \setminu X|$ -> $r(F \cap X) = |F_{E \setminus X}|$
page 56, Proposition 5.20 and its proof: replace $r$ by $m$
page 57, lines 6-11: replace "If $(X,Y) ... (until end of the paragraph)" by "The same argument used on dual matroid gives cyclical $k$-connectivity of M.
line -12: $k$-separation -> $k'$-separation
page 59, line 14: k -> k'
page 60, line 2: $U_{r,n}$ -> $U_{m,n}$ and $2r-1$ -> $2m-1$
lines -16--15: replace r by m
line -8: delete simple
page 67, line -9: third, lust but one and last -> first, forth and last
line -8: obtain $c=1$ -> obtain $a=1$ and $a=1$ -> $c=1$
page 69, line 3: parallel edges -> parallel elements
page 70, line -8: $C$ -> $C \setminus B$
line -5: $C$ -> $C \setminus B$
page 73, line 4: replace the matrixed by the transposed one
page 88, line -10: \lambda -> M
page 105, line 4: "An \sigma-interpretation" -> "A \sigma-interpretation"