Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
34 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 ...
Jonathan McDonald's user avatar
1 vote
0 answers
31 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 ...
Jonathan McDonald's user avatar
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 ...
sor3n's user avatar
  • 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 $...
sor3n's user avatar
  • 15
1 vote
2 answers
76 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 ...
user758193's user avatar
0 votes
1 answer
34 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 ...
sor3n's user avatar
  • 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 ...
yeetcode's user avatar
  • 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 ...
tses's user avatar
  • 225
2 votes
0 answers
71 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^{\...
Jose Brox's user avatar
  • 4,876
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 ...
Intuition's user avatar
  • 3,181
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?
Emptymind's user avatar
  • 2,069
1 vote
0 answers
22 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 ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
46 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 ...
Intuition's user avatar
  • 3,181
0 votes
0 answers
88 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 $\...
Intuition's user avatar
  • 3,181
1 vote
1 answer
141 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 ...
Hope's user avatar
  • 95
0 votes
1 answer
59 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 ...
Intuition's user avatar
  • 3,181
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 ...
Intuition's user avatar
  • 3,181
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 ...
Intuition's user avatar
  • 3,181
3 votes
1 answer
97 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 ...
Hope's user avatar
  • 95
-1 votes
1 answer
50 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 ...
Hope's user avatar
  • 95
2 votes
1 answer
86 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$ ...
Hope's user avatar
  • 95
1 vote
1 answer
81 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 ...
Hope's user avatar
  • 95
2 votes
1 answer
89 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.$\...
Intuition's user avatar
  • 3,181
2 votes
1 answer
80 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 ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
65 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 ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
60 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{...
Emptymind's user avatar
  • 2,069
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) =...
Intuition's user avatar
  • 3,181
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 ...
Apple's user avatar
  • 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 ...
Intuition's user avatar
  • 3,181
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 ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
108 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) = ...
Intuition's user avatar
  • 3,181
2 votes
1 answer
58 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$- ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
69 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 ...
Snowflake's user avatar
  • 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 ...
Intuition's user avatar
  • 3,181
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. ...
Intuition's user avatar
  • 3,181
2 votes
1 answer
87 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\...
Intuition's user avatar
  • 3,181
0 votes
1 answer
94 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". ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
48 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 ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
65 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 (...
Intuition's user avatar
  • 3,181
0 votes
1 answer
107 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 ...
Intuition's user avatar
  • 3,181
0 votes
1 answer
56 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 ...
Intuition's user avatar
  • 3,181
1 vote
1 answer
164 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 ...
user avatar
1 vote
1 answer
111 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(...
Emptymind's user avatar
  • 2,069
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) \...
Emptymind's user avatar
  • 2,069
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) \...
Emptymind's user avatar
  • 2,069
0 votes
1 answer
92 views

proving that $r(X \cup Y) = r(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) \...
Emptymind's user avatar
  • 2,069
1 vote
1 answer
112 views

Constructing a basis for a matroid with a circuit in it.

Here is the question I am trying to solve (Matroid Theory, second edition by Martin Oxley, Chapter 1, section 2): Prove that if $C$ is a circuit of a matroid $M$ and $e \in C,$ then $M$ has a basis $B$...
Emptymind's user avatar
  • 2,069
0 votes
1 answer
109 views

The intersection of all of the flats containing $X$ equals $cl(X).$

Here is the question I am trying to solve (Matroid Theory, Second edition, Chapter 1, section 4 ): Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the ...
Emptymind's user avatar
  • 2,069
2 votes
1 answer
69 views

Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
hedgehog0's user avatar
0 votes
1 answer
38 views

Characterizing paving matroids in terms of their bases.

Here is the question I am trying to solve: Characterize paving matroids in terms of their collections of independent sets and in terms of their collection of bases. What exactly does it mean to ...
Emptymind's user avatar
  • 2,069

1
2 3 4 5 6