Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
88 views

Invariants in the ring of coinvariants

This seems to be part of folklore, but I can't find a proof anyqhere, only references to "a very nice proof of a special case by Arkady Berenstein in a seminar I attended in 1989". Okay, here it goes....
1
vote
0answers
59 views

Murnaghan-Nakayama rule for general dimension of a hook

Let $m,r\in \mathbb{N}, n=rm$. The character of symmetric group $\chi^{\lambda}$ where $\lambda$ is of the from $(k,1^{n-k})$ evaluated at the conjugacy class of $S_{n}$ of the from $(r,\ldots,r)$, ...
1
vote
0answers
35 views

How does the sum of closed walks change when a new vertex is added to a subgraph?

Suppose I calculate the sum of all closed walks from vertex i in a subgraph of some graph (the subgraph is composed of a subset of vertices from the graph and all edges between those vertices from the ...
1
vote
1answer
426 views

Is there a explicit formula for the number of Semi-standard Young Tableaux over $\{1,\dots,n\}$ for a given partition $\lambda$ and a given type $\mu$

I was given an exercise to give all SSYT over $\{1,\dots,12\}$ of shape $\lambda=(4,4,3,1)$ and type $\mu=(4,2,2,2,2,0,\dots,0)$. Now I was wondering if there is an formula to say something about the ...
2
votes
1answer
126 views

Counting monic irreducible polynomials of a particular degree without use of finite fields?

I know that every irreducible polynomial over $\mathbb F_p[x]$ of degree equal to the degree $m$ of a finite field $\mathbb F_{p^{m}}$ has a root in the field. Using this result we can count the ...
0
votes
2answers
103 views

What is the expected value of the product of the number of heads you get and the number of tails you get when you flip n coins? [closed]

Ex. If you get $h$ heads and $n-h$ tails the product would be $n(n-h)$ I want to know the expected value of this product.
4
votes
2answers
178 views

What do we mean when we say the Schur functions form a basis.

This has always bugged me. When we are examining symmetric functions (or polynomials if you prefer finitely many variables), we have an easy choice of basis with the monomial symmetric functions. As ...
2
votes
2answers
276 views

Reference request: Representation theory over fields of characteristic zero

Many representation theory textbooks and online resources work with the field of complex numbers or more generally algebraically closed fields of characteristic zero. I am looking for a good textbook ...
1
vote
2answers
63 views

Exercise on number of walks in a graph

The following is an exercise (Exercise #2 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics. Let $G$ be a finite graph (allowing loops and multiple edges). Suppose that ...
4
votes
3answers
197 views

Graph Theory - Application of Kirchoff's Matrix Tree Theorem

Calculate the number of spanning trees of the graph that you obtain by removing one edge from $K_n$. (Hint: How many of the spanning trees of $K_n$ contain the edge?) I know the number is $(n-2)n^{...
1
vote
0answers
91 views

Permutations That Are Conjugate with an Element From Stabilizer of Another Permutation

We know that permutations, elements of the symmetric group on a finite set with n elements, are conjugate iff they have the same cycle structure. My question is that given two permutations that are ...
-2
votes
2answers
136 views

The Sum of all four(4) digit numbers formed with the digits [closed]

The Sum of all four(4) digit numbers formed with the digits one(1),three(3),three(3), and zero(0) Without repeating them
1
vote
1answer
42 views

Distance Regular Graphs

Given that $\Gamma=(X,R)$ denote a distance-regular graph with diameter $D$ and valency $k=b_0$. How will I show that $k = a_i + b_i + c_i$ for all $0 \leq i \leq D$? Trying to make use of the ...
2
votes
0answers
182 views

Necklace polynomial recurrence relation

Let the number of monic, irreducible polynomials of degree $n$ over $F_q$ be $f(n)$, then $f(1)=q$, and to calculate $f(n)$, I would count the number of monic, reducible polynomials of degree $n$ this ...
1
vote
0answers
65 views

Extending an Analytic Proof for Lagrange Inversion of Formal Power Series

In Appendix A.6 of Sedgewick and Flajolet's Analytic Combinatorics, the authors present a proof of the assertion that if we have formal power series $y(z)$ and $\phi(z)$ (where the constant term of ...
0
votes
1answer
76 views

Calculating the Most Reduced Sets in a Set of Sets

I'm having trouble solving this problem efficiently: Let's say we have the following sets {1, 2, 3} {1, 2} {2, 3} {1} We want to eliminate those sets which are ...
4
votes
1answer
63 views

Prove the bijections between the following $(p,q,r)$-shuffles

I am reading the book "From Calculus to Cohomology: De Rham cohomology and characteristic classes" Let $p, q, r$ be nonnegative integers. It says, (for those who own the book, on pg 10) without ...
2
votes
1answer
159 views

What is the following way of indexing permutations called?

I'm sure this is well-known but I don't know where to look in order to find it. Consider a permutation, e.g. $\sigma = 2 1 4 3$ in one-line notation. This corresponds to a monotone triangle via \...
0
votes
0answers
28 views

All the partitions of a natural number without restricting commutativity

Let us consider an infinit-degree polynomial, $p\left( \mathbf{x} \right)$: $$p\left( \mathbf{x} \right)=\sum\limits_{\begin{smallmatrix} \mathbf{v}\in {{\mathbb{N}}^{n}} \\ {{v}_{1}}+{{v}_{2}}+.....
1
vote
1answer
36 views

All partitions of a natural number without supposing commutativity [closed]

Please, help me, how to generate all the partitions of a natural number if we ignore the commutativity. Thank you for your help!
1
vote
0answers
65 views

Two kinds of Fuss ballot numbers?

This is a newbie question (I have never had much to do with Catalan combinatorics), so be prepared for an easy answer. Consider the directed graph whose vertices are pairs $\left(a,b\right)$ of ...
1
vote
0answers
151 views

Count the number of functional digraphs with special restrictions

Given a set of $n$ nodes, how can I count the number of possible functional di-graphs whose biggest connected component contains k node? With a restriction that no node can have an edge point to ...
8
votes
0answers
139 views

Inequality for hook numbers in Young diagrams

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$ define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...
1
vote
1answer
83 views

Known results on the relationship between automorphisms and spectrum of a graph?

I recently saw this post from Ed Pegg on Math Stack Exchange about integral graphs with trivial automorphism groups. I am interested in trying to construct smaller such graphs - at the very least, I ...
3
votes
0answers
39 views

Calculating determinants

Let $n\geq 2$ be an integer and let $\Sigma$ be the collection of all $2$-subsets (a 2-set is a set that contains $2$ elements) of $[n]=\{1,2,\dots,n\}$, thus $\Sigma$ contains $\binom{n}{2}$ elements....
3
votes
0answers
60 views

Example of shellable and non-shellable simplicial complexes with the same $f$-vector

I need to construct two pure simplicial complexes with the same $f$-vector such that one is shellable and one isn't. I think we can try two-dimensional simplicial complexes, I can find two simplicial ...
0
votes
1answer
31 views

Colexiographic ordering problem

I have two vectors, $(b_1,\cdots,b_k)$ and $(ms_1,\cdots,ms_{2^k})$. Let $\overline{b_l} = (1-b_l)$ be the falsity term of $b_l$. As an example consider $k=3$, then the ordering I require is: $m_1 = ...
0
votes
1answer
555 views

What book about algebraic combinatorics is it?

Recently I found a fragment of a book about algebraic combinatorics on the internet coincidentally. And I found it's really an excellent resource of learning polynomial method, about Combinatorial ...
2
votes
0answers
67 views

Sum of Roots of Unity With Weighted Exponents

I have the following conjecture that I want to believe has some sort of classical result associated to it, but have yet to find any such evidence. Let $\ell,r\in\mathbb{Z}^+$, and fix $w_1,\ldots,w_{\...
0
votes
0answers
91 views

Eulerian Numbers Generalization

Does anyone have a combinatorial proof for the following identity: $\sum_{i=j}^n S(n,n-j)(n-j)!(-1)^{n-j-1}=A(n,j)$. I have tried using ordered set partitions with inclusion/exclusion, but I have yet ...
2
votes
1answer
173 views

nth power symmetric polynomial in terms of Schurs polynomial

The Schur's polynomial forms the basis of the symmetric algebra so does the power symmetric function. nth power symmetric function are the function of the form $\sum_i x_i^n$. Let $\lambda \vdash n$ ...
0
votes
0answers
35 views

Can i define eigenvalues and determinant for a 3D matrix and Is it well defined? [duplicate]

Can i define eigenvalues for a 3D matrix? I want to try to use this structure on rubik's cube to find out what is the minimum number of moves to solve it! I know rubik's cube is agroup but i dont know ...
1
vote
0answers
37 views

On factorization theorem of toric birational morphisms

Let $X_{\Sigma'} \to X_{\Sigma}$ be a toric birational morphism between smooth and complete toric varieties induced by a regular subdivision $\Sigma' \leq \Sigma$, i.e. every cone in $\Sigma'$ is ...
1
vote
1answer
83 views

prove a polynomial identity..

The equation is that $h_m(x_1, \cdots, x_n, a)-h_m(x_1, \cdots, x_n, b)=(a-b)h_{m-1}(x_1, \cdots, x_n, a, b)$ where $h_m$ is a complete homogeneous symmetric polynomial. See and find several ...
2
votes
0answers
170 views

Radon transform: intution and usefulness?

In Stanley's Algebraic Combinatorics, Chapter 2 is spent discussing the application of the Radon transform to determine the eigenvalues and eigenvalues of the adjacency matrix of $C_n$, the $n$-cube. ...
1
vote
1answer
346 views

Five people are sitting around a table. Let x be the number of people sitting next to at least one woman and y be the number of people…

5 people are sitting around a table. Let x be the number of people sitting next to at least one woman and y be the number of people sitting next to at least one man. How many possible values of the ...
14
votes
4answers
905 views

Property of a polynomial with no positive real roots

The following is an exercise (Exercise #3 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics. Let $P(x)$ be a nonzero polynomial with real coefficients. Show that the ...
9
votes
2answers
63 views

Given a matrix $A$ such that $A^{\ell}$ is a constant matrix, must $A$ be a constant matrix?

This problem originates from an exercise in Richard Stanley's Algebraic Combinatorics. The exercise in the text (Chapter 3, Exercise 2(a)) asks Let $G$ be a finite graph (allowing loops and ...
1
vote
2answers
376 views

Expressions for symmetric power sums in terms of lower symmetric power sums

The Newton symmetric power sums $p_k(x_1, \ldots, x_n)$, for $k \geq 1$, are given by $$ p_k(x_1, \ldots, x_n) = \sum_{i=1}^n x_i^k. $$ Do you know if it's possible to express $p_k$ in terms of (non-...
13
votes
0answers
319 views

How to prove this $p^{j-\left\lfloor\frac{k}{p}\right\rfloor}\mid c_{j}$

Let $p$ be a prime number and $g\in \mathbb{Z}[x]$. Let $$\binom{x}{k}=\dfrac{x(x-1)(x-2)\cdots(x-k+1)}{k!} \in \mathbb{Q}[x]$$ for every $k \geq 0$. Fix an integer $k$. Write the integer-valued ...
1
vote
0answers
44 views

How to prove Crapo's Lemma

Crapo's Lemma states: Let $X$ be a subset of a lattice $L$, and let $n_k$ be the number of $k$-element subsets of $X$ with join equal to $\hat{1}$ and meet equal to $\hat{0}$. Then $$\sum_k (-1)^{...
12
votes
1answer
4k views

Undergrad-level combinatorics texts easier than Stanley's Enumerative Combinatorics?

I am an undergrad, math major, and I had basic combinatorics class before (undergrad level.) Currently reading Stanley's Enumerative Combinatorics with other math folks. We have found this book ...
1
vote
0answers
74 views

How many degree m elements in the exterior algebra on n generators over a finite field, vanish when raised to the r-th power?

Let $R=\Lambda_{\mathbb{F}_p}[e_1,...,e_n]$ be the exterior algebra on $n$ generators over the finite field with $p$ elements (this arises naturally as the mod-p cohomology ring of the $n$-dimensional ...
3
votes
1answer
114 views

Is there a synthetic definition of the $0$-Hecke monoid of $S_n$?

Background. Let $n$ be a nonnegative integer, and let $S_n$ denote the $n$-th symmetric group. The $0$-Hecke monoid $H_0\left(S_n\right)$ is defined to be the monoid given by generators $t_1, t_2, \...
1
vote
0answers
32 views

Reference for a Dickson Determinant Polynomial

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation} ...
1
vote
1answer
312 views

Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$

A Paley graph is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$. I need to prove that, and obtain the parameters too. Proving it is regular valency $\frac{p-1}{2}$ is ...
1
vote
1answer
83 views

No triangles or rectangles in a Moore graph of diameter 2.

Can somebody explain why there cannot be any triangles or squares in a Moore graph with diameter 2? This was stated without proof in my class.
2
votes
0answers
80 views

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
1
vote
0answers
49 views

Orbital dimension of the action of $S_n$ on 2-subsets

I have a question on a proof in a paper on the orbital dimension of a permutation group. Let $G \le S^\Omega$ be a permutation group. A base for $G$ is a subset $\Sigma \subseteq \Omega$ for which ...
8
votes
1answer
550 views

A question on Derangement Combinatorics

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the ...