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
1
vote
0
answers
30
views
Exercise 11.1 in Algebraic Combinatorics by Stanley
Let $\mathcal{C}_{D} = \mathcal{C}$ denote the cycle space, or the space of all circulations, on some digraph $D$. Let $C_n$ denote the $n$-dimensional hypercube, and $\mathfrak{o}$ denote some ...
3
votes
0
answers
42
views
Exercise 2.2 In Stanley's Algebraic Combinatorics
This is Exercise $2.2$ In Stanley's Algebraic Combinatorics. I don't have much work to show because despite being stuck on this problem for a long time, I haven't got a clue how to start.
$\mathcal{C}...
- 3,100
0
votes
1
answer
36
views
Exercise 9.6 in Algebraic Combinatorics by Stanley
Exercise 6 in chapter 9 of Algebraic Combinatorics by Stanley: Let $G$ be a finite graph on $p$ vertices with Laplacian matrix $L(G)$. Let $G'$ be obtained from $G$ by adding a new vertex $v$ and ...
2
votes
1
answer
51
views
Regarding the number of variables in Symmetric Functions
I'm studying Symmetric Functions and I came across a doubt that could be considered stupid but I need clarifications.
In the course I'm following we introduced symmetric functions as formal series of ...
4
votes
1
answer
57
views
Exercise 8.6 of Algebraic Combinatorics by Stanley
Problem 6 in Chapter 8 of Algebraic Combinatorics by Stanley: Show that the total number of standard Young tableaux (SYT) with $n$ entries and at most two rows is ${n \choose \lfloor n/2 \rfloor}$. ...
1
vote
1
answer
38
views
Exercise 7.2 in Algebraic Combinatorics by Stanley
This is exercise 2 in chapter 7 of Algebraic Combinatorics by Stanley.
For part (a), I first found the entire automorphism group. By labeling the root 1, and then numbering off the remaining vertices ...
1
vote
0
answers
37
views
Exercise 3.1 of Algebraic Combinatorics by Richard Stanley
Exercise 3.1: Let $G$ be a (finite) graph with vertices $v_1, \ldots, v_p$. Assume that some power of the probability matrix $M(G)$ defined by $(3.1)$ has positive entries. (It's not hard to see that ...
0
votes
0
answers
116
views
find the general solution the recurrence equation $b_n = 3b_{n-1} - b_{n-3}$
here are the steps I have done to try and find the general solution of this relation:
$$ b_n = 3b_{n-1} - b_{n-3}\\ = b^n = 3b^{n-1} - b^{n-3}$$
then divide by $b^{n-3}$ to get $$b^3 = 3b^2 - 1$$
then ...
- 15
1
vote
1
answer
44
views
find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom
here is the full question:
Use inclusion/exclusion to find the number of ways of distributing 30
students into six classrooms assuming that each classroom has a maximum capacity
of six students.
Let $...
- 15
1
vote
2
answers
81
views
Identity of Schur polynomials
Let $p_n$ be the power sum symmetric polynomial,
$$p_n=x_1^n+x_2^n+\dots x_n^n$$
in $n$ variables, and let $s_\lambda$ be the Schur polynomials. I am new to Schur polynomials so I'm not sure what ...
- 83
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
0
votes
0
answers
14
views
Isometric automorphisms of the ring of symmetric functions
I was trying to understand how special the $\omega$ involution on the ring of symmetric functions $\Lambda$ or $\Lambda^n$ (restriction to $n$ variables, just in case if by some magic, the situation ...
- 143
1
vote
0
answers
16
views
Composition of homomorphisms of association schemes
In Zieschang's "Theory of Association Schemes", in section 5.2, he remarks that the composition of homomorphisms is not always a homomorphism. I've been struggling to find an example of that ...
- 255
2
votes
0
answers
81
views
Restriction of induced representation over a Young subgroup and Littlewood-Richardson coefficients
I'm inexperienced in the representation theory of the symmetric group, so please correct my possible mistakes. Fix $m\leq n$, $G:=S_n$ and $H:=S_m\times S_{n-m}$ as a Young subgroup of $G$. Let $V^{\...
- 4,886
0
votes
0
answers
23
views
Affiness, $U_{2,4}$ and $M(K_4).$
I do not know why $M(K_4)$ is not affine over $GF(2)$ or $GF(3)$ but it is affine over all fields with more than 3 elements. I proved that $U_{2,4}$ is $\mathbb F$-representable iff $|\mathbb F| \geq ...
- 3,139
0
votes
0
answers
20
views
Lift and frame matroids.
I want to read more about lift matroid and frame matroid and their flats and relations to signed graphs, do you know any basic resources for this?
- 2,087
1
vote
0
answers
23
views
Characteristic polynomial and bounded regions.
I know that the number of bounded regions of a homogeneous hyperplane arrangement $\mathcal{A}$(a collection of n hyperplanes) in $\mathbb R^d$is ${ n - 1 \choose d}$ but how can this be expressed in ...
- 3,139
0
votes
1
answer
53
views
Understanding contraction in hyperplane arrangements.
Here are two figures that shows a hyperplane arrangement's contraction (this is from McNulty book, "Matroids, a geometric introduction"):
I am not sure why a became a line in the right ...
- 3,139
0
votes
0
answers
90
views
Hyperplane Areangements and contraction.
I am trying to understand an idea presented in McNulty book, matriods a geometric introduction about the new hyperplane arrangement $\mathcal{A}^{''} = \{ H \cap H_x | H \in \mathcal{A}\}$ where $\...
- 3,139
1
vote
1
answer
144
views
No minors isomorphic to $U_{0,1}$ and $U_{1,2}.$
I am trying to find all the matroids having no minors isomorphic to $U_{0,1}$ and $U_{1,2}.$
I know that the matroid $U_{0,n}$ is a matroid of rank zero with n edges and so it is just a vertex with n ...
- 95
0
votes
1
answer
60
views
Contraction, loops and flats.
This idea is being used a lot, but I cannot justify why it is correct:
If M is a matroid and $T$ a subset of $E(M).$ Then $M/T$ has no loops iff $T$ is a flat of $M.$
I know how to proof that in a ...
- 3,139
0
votes
1
answer
46
views
The basis of a regular matroid.
I know that a regular matroid is one that can be represented by a totally unimodular matrix.
I also know that a rank r totally unimodular matrix is a matrix over $\mathbb R$ for which every submatrix ...
- 3,139
1
vote
1
answer
56
views
affine geometries that are self-dual matroids.
I want to know which of the affine geometries $AG(n,q)$ are self-dual matroids?
I have proved before that uniform matroids $U_{n,m}$ that are self duals are those who satisfies that $m = 2n.$ I am ...
- 3,139
3
votes
1
answer
101
views
Understanding how to find the dual of a matroid.
I am trying to understand the following picture of a matroid and its dual but I found myself not understanding exactly what we are doing to find the dual:
]1
Roughly speaking, according to some ...
- 95
-1
votes
1
answer
52
views
what will happen if we contract an element in a uniform matroid? [closed]
Are the parallel elements in a matroid just behaving like loops? If so, why?
For example, in $U_{2,3}$ if we contract an element what will happen? In $U_{2,2}$ if we contract an element what Will ...
- 95
2
votes
1
answer
87
views
Partition lattice properties and an invariant.
I am trying to guess the value of the beta invariant of the partition lattice $\pi_4$ if I know the following information:
For any matroid $M,$ I know that
1- $\beta(M) \geq 0.$
2- $\beta(M) > 0$ ...
- 95
1
vote
1
answer
82
views
what will happen to the uniform matroid $U_{2,m}$ if we remove an element from it?
I am trying to figure out what will happen to the uniform matroid $U_{2,m}$ if we remove an element e from it, where e is neither a coloop nor a loop. I am guessing that it will become disconnected ...
- 95
2
votes
1
answer
94
views
Show that $C^*(e,B)$ is the unique cocircuit that is disjoint from $B - e.$
I want to prove the following question:
Let $B$ be a basis of a matroid $M.$ If $e \in B,$ denote $C_{M^*}(e, E(M) - B)$ by $C^*(e,B)$ and call it the fundamental cocircuit of $e$ with respect to $B.$\...
- 3,139
2
votes
1
answer
82
views
Showing the isomorphism between (the geometric lattice)$\pi_n$ and the lattice $\mathcal{L}(M(K_n)).$
Here is the question I am trying to solve:
Show that the lattice of flats of $M(K_n)$ is isomorphic to the partition lattice $\pi_n$. Definition: $\pi_n$ is the set of partitions of $[n]$, partially ...
- 3,139
0
votes
1
answer
68
views
if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis.
here is the question I am trying to solve:
In a matroid $M,$ if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis.
I know how to prove that a set ...
- 3,139
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
0
votes
1
answer
57
views
Show that a matroid $M$ is connected iff, for every pair of distinct elements of $E(M),$ there is a hyperplane avoiding both.
Here is the question I am thinking about:
Show that a matroid $M$ is connected iff, for every pair of distinct elements of $E(M),$ there is a hyperplane avoiding both.
It is in James Oxley book in ...
- 3,139
1
vote
1
answer
167
views
circuit and a cocircuit can not have an odd number of common elements.
Here is the question I am trying to solve:
Show that, in a binary matroid, a circuit and a cocircuit can not have an odd number of common elements.
Here are the required definitions:
A binary matroid ...
user965463
1
vote
1
answer
112
views
If $X \subseteq Y$ and $r(X) = r(Y),$ then $cl(X) = cl(Y).$
Here is the question I am trying to understand its solution:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(e)$ If $X \subseteq Y$ and $r(...
- 2,087
1
vote
0
answers
64
views
Proving that $r(cl(X) \cup cl(Y)) = r(cl(X \cup Y))$.
Here is the question I am trying to prove:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
- 2,087
1
vote
1
answer
89
views
proving that $r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)).$
Here is the question I am trying to prove:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
- 2,087