Questions tagged [algebraic-combinatorics]
For problems involving algebraic methods in combinatorics (especially group theory and representation theory) as well as combinatorial methods in abstract algebra.
265
questions
0
votes
1
answer
68
views
What is the definition of affine independence then?
The following is the definition of affine dependence (This definition is from James Oxley book, second edition "matroid theory")
Definition of affine dependence:
A multiset $\{ \underline{...
- 2,087
0
votes
1
answer
36
views
Let $A\subset B$ be flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$.
I want to prove the following lemma:
Let $r$ denotes the rank.
Lemma. Let $A\subset B$ be any flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$.
My thoughts are:
I know that $cl(A) =...
- 3,139
3
votes
0
answers
131
views
Taylor Expansion of the Polynomial in Flajolet’s Fundamental Lemma
I am currently looking at the proof of Flajolet’s Fundamental Lemma. Before I phrase the question, I need to review the definition of $(0,k)$-path and define its weight.
Define $(0,k)$-path as the ...
- 95
0
votes
1
answer
82
views
Proving that $ \beta(M) = \beta (M - e) + \beta (M /e).$
Here is the statement I am trying to prove:
If $e \in E$ is neither a loop nor an isthmus, then $$ \beta(M) = \beta (M - e) + \beta (M /e).$$
Here are all the properties I know about the Crapo's beta ...
- 3,139
0
votes
1
answer
71
views
Why always the Crapo beta invariant value greater than or equal zero?
Here are the definitions of the Crapo beta invariant I know:
My definition of the Crapo's beta invariant of a matroid from the book "Combinatorial Geometries" from page 123 and 124 is as ...
- 3,139
1
vote
1
answer
111
views
Philip Hall's theorem
Here is the theorem I want to prove:
For $x,y \in P$ and $i \geq 0,$ let $c_i(x,y)$ be the number of chains $x=x_0 < x_1 < \dots < x_i = y$ of length $i$ from $x$ to $y.$ Let $$\phi (x,y) = ...
- 3,139
2
votes
1
answer
61
views
an $\mathbb F$- representation of the matroid $M_1 \oplus M_2.$
Suppose that $A_1$ and $A_1$ are $\mathbb F$- representations of the matroids $M_1$ and $M_2$ respectively, show that
$$\begin{matrix}
A_1& 0\\
0 & A_2
\end{matrix}$$
is an $\mathbb F$- ...
- 3,139
1
vote
1
answer
75
views
Trace of power of matrix (arising from number of closed walks)
Let $G_n$ be the graph obtained from the $n-$cube graph $C_n$ by adding one extra edge between each vertex and its antipode (vertex whose label has all $0$'s and $1$'s switched) Note: The $C_n$ graph ...
- 326
0
votes
1
answer
83
views
Finding an $\mathbb R$-representation for $M^*.$
Here is something I want to learn ( Problem #2.2.7 in Matroid Theory, first edition( page 88 ) , by James Oxley:
Finding an $\mathbb R$-representation for the dual matroid $M^*$ when $M$ is the vector ...
- 3,139
0
votes
2
answers
120
views
Show that no row of $A$ contains exactly one non-zero entry.
Here is the question I am trying to tackle:
Let $A$ be a non-zero matrix over a field $\mathbb F$ and suppose that $M[A]$ has no coloops. Show that no row of $A$ contains exactly one non-zero entry.
...
- 3,139
2
votes
1
answer
88
views
prove that $M\big[ \frac{A_1}{A_2}\big] = M[A_1].$
Here is the question I am trying to tackle:
For $i = 1,2,$ let $A_i$ be an $m_i \times n$ matrix over a field $\mathbb F.$ If every row of $A_2$ is a linear combination of rows of $A_1,$ prove that $M\...
- 3,139
0
votes
1
answer
95
views
Determining all self-dual uniform matroids.
I want to determine all self-dual uniform matroids; I know that the dual of a uniform matroid $U_{r,n}$ is $U_{n - r,n}$ by Example $2.1.4$ in James Oxley, second edition, "Matroid Theory". ...
- 3,139
0
votes
1
answer
52
views
The relation between contraction and deletion in a matroid.
Here is the relation I have seen a lot in the books, but I am not sure why it is always true:
If $T \subseteq E(M)$ then $$M \setminus T = (M^* / T)^* \quad\quad (*)$$
I know that contraction is ...
- 3,139
0
votes
1
answer
67
views
Why every component of a loopless matroid is flat?
Why every component of a loopless matroid is flat?
I know that the rank of a loop in a matroid is zero and I read that: A loop is an element of a matroid that is not contained in any independent set (...
- 3,139
0
votes
1
answer
108
views
The relation between the closure and the contraction of a matroid M.
Here is the relation I am trying to justify:
$cl_{ M/T}(X) = cl_M(X \cup T) - T$ for all $X \subseteq E - T.$
Why this relation true?
Any proof will be greatly appreciated!
**Here are all what I know ...
- 3,139