# 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.

261 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
1 vote
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 ...
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
44 views

• 4,876
23 views

• 3,181
1 vote
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 ...
• 95
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 ...
• 3,181
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,181
1 vote
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,181
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 ...
• 95
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 ...
• 95
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$ ...
• 95
1 vote
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 ...
• 95
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.$\...
• 3,181
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 ...
• 3,181
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 ...
• 3,181
60 views

• 3,181
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
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,181
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,181
1 vote
108 views

• 3,181
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 (...
• 3,181
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 ...
• 3,181
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 ...
• 3,181
1 vote
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 ...
1 vote
111 views

• 2,069
1 vote
89 views

• 2,069
1 vote
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$...
• 2,069
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 ...
• 2,069
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 ...