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.

15
votes
3answers
451 views

A conference uses $4$ main languages. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.

A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know. Source: ...
14
votes
6answers
753 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
14
votes
4answers
918 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 ...
13
votes
3answers
2k views

Hartshorne Problem 1.2.14 on Segre Embedding

This is a problem in Hartshorne concerning showing that the image of $\Bbb{P}^n \times \Bbb{P}^m$ under the Segre embedding $\psi$ is actually irreducible. Now I have shown with some effort that $\psi(...
13
votes
0answers
321 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 ...
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 ...
10
votes
2answers
2k views

Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions ...
10
votes
1answer
161 views

why $\frac{f_n}{f_kf_{n-k}}$ is an integer for this sequence

New Zealand 2013 TST problem: Let $r$ and $s$ be positive integers. Define $a_0 = 0$, $a_1 = 1$, and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$. Let $f_n = a_1a_2\cdots a_n$. Prove that $\dfrac{f_n}{...
10
votes
1answer
348 views

Motivation/intuition behind using linear algebra behind these combinatorics problem

What is the motivation behind using linear algebra in these three problems ? A pair $(m,n)$ is called nice if there is a directed graph with (self edge are allowed, but multiple edge are not allowed)...
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 ...
9
votes
1answer
377 views

Powers of a simple matrix and Catalan numbers

Consider $m \times m$ anti-bidiagonal matrix $M$ defined as: $$M_{ij} = \begin{cases} -1, & i+j=m\\ \,\,\ 1, & i+j=m+1\\ \,\,\, 0, & \text{otherwise} \end{cases}$$ Let $S_n$ stand ...
8
votes
2answers
221 views

Proving an identity for complete homogenous symmetric polynomials

Probably everybody knows the expression: $$ \sum_{k_1,k_2\ge0}^{k_1+k_2=k}a_1^{k_1}a_2^{k_2}=\frac{a_1^{k+1}-a_2^{k+1}}{a_1-a_2}, $$ where $a_1\ne a_2$ is assumed. It seems that it can be further ...
8
votes
1answer
554 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 ...
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 $...
7
votes
3answers
219 views

How many $n$-pointed stars are there?

Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars ...
7
votes
2answers
241 views

Given a list of $2^n$ nonzero vectors in $GF(2^n)$, do some $2^{n-1}$ of them sum to 0?

Let $G=(\mathbb{Z/2Z})^n$ written additively, $n>1$. (you can think of it as $\mathbb{F}_{2^n}$ but I didn't find that useful... yet) Let $v_i$ be nonzero elements of $G$ for $i \in \{1 \dots 2^n \...
7
votes
0answers
309 views

Uses of Chevalley-Warning

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...
6
votes
3answers
152 views

We have $n$ real numbers around the circle and among any consecutive 3 one is AM of the other two. Then all the numbers are the same or $3\mid n$.

There are $n$ real numbers around the circle and among any consecutive 3 one is arithmetic mean of the other two. Prove that all the numbers are the same or $3\mid n$. Hint was to use a linear ...
5
votes
3answers
269 views

“Binomial coefficients” generalized via polynomial iteration

This is a question I will answer myself immediately by repeating one of my old AoPS posts, since the latter post no longer renders on AoPS. Convention. In the following, whenever $A$ is a ...
5
votes
2answers
201 views

$\eta$-value of a partition and its meaning

The $\eta$-value of an integer partition $\lambda = \big( \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k \geq 0 \big)$ is defined as \begin{equation} \eta \big( \lambda \big) \ := \ \sum_{i=1}^k ...
5
votes
1answer
399 views

Properties of the 'forgotten' symmetric polynomials

In I.G. Macdonald "Symmetric Functions and Hall Polynomials" pg.22, the forgotten symmetric functions $f$ are introduced very briefly as the result of applying an involution $\omega$ to the monomial ...
5
votes
2answers
148 views

There are $n$ different $3$-element subsets $A_1,A_2,…,A_n$ of the set $\{1,2,…,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not=...
5
votes
1answer
153 views

Young projectors in Fulton and Harris

In Section 4 of Fulton and Harris' book Representation Theory, they give the definition of a Young tableau of shape $\lambda = (\lambda_1,\dots,\lambda_k)$ and then define two subgroups of $S_d$, the ...
4
votes
1answer
5k views

Use of rook polynomials

Use rook polynomials to count the number of permutations of $(1,2,3,4)$ in which $1$ is not in the second position, $2$ is not in the fourth position, and $3$ is not in the first or fourth position. ...
4
votes
2answers
181 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 ...
4
votes
3answers
197 views

We are given an $18\times 18$ table, all of whose cells may be black or white.

We are given an $18\times 18$ table, all of whose cells may be black or white. Initially all the cells are colored white. We may perform the following operation: choose one column or one row and ...
4
votes
3answers
200 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^{...
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 ...
4
votes
1answer
88 views

Can the natural proof of this algebraic identity be simplified?

Let $x^4+c_3x^3+c_2x^2+c_1x+c_0$ be a real polynomial with no real root. Then there are two pairs of conjugate complex roots, $a_1\pm b_1 i$ and $a_2\pm b_2 i$, and one has the identity $$ c_1^2-...
4
votes
1answer
82 views

Prescriptive version of counting hyperplane arrangements

In Hyperplane arrangement theory, Zaslavsky's Theorem necessarily bounds the number of bounded and unbounded regions in the complement of a real hyperplane arrangement. While this counting theorem is ...
4
votes
1answer
123 views

Interpretation of the numerator of the Hilbert series?

Let $R$ be a finitely generated graded ring over a field $k$. Let $R_\ell$ be the degree-$\ell$ homogeneous component of $R$. By the Noether normalization theorem, $R$ is finite over a graded ...
4
votes
0answers
74 views

Constant sum of characters

Let $q$ be a prime power and $\omega=\exp(2\pi i/q)$. For a fixed $y\in\mathbb{Z}_q^n$, the map $$\mathbb{Z}_q^n\ni x\mapsto \omega^{x\cdot y}=\omega^{x_1y_1+\dots+x_ny_n}$$ is a character of $\...
4
votes
0answers
61 views

Is there anywhere some explicit Bruhat decompositions are written down?

Question in title: most places I see Bruhat decompositions treated they're only briefly mentioned and no examples are given. Also, I calculated the following regarding the Bruhat decomposition of $\...
3
votes
1answer
96 views

Classification of groups whose any non-trivial element can be associate to another to generate all

Question: What are the groups (possibly infinite) $G$ satisfying the following property? $$ \forall g \in G \setminus \{ e \} \ \exists g' \in G \text{ such that } \langle g,g' \rangle = G.$$ ...
3
votes
1answer
97 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
3
votes
1answer
82 views

Prove that $h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$

Let $h_r\left(x_1,\ldots,x_n\right)$ denote the $r$-th complete homogeneous symmetric polynomial in the $n$ indeterminates $x_1, \ldots, x_n$ (that is, the sum of all degree-$r$ monomials in these $n$ ...
3
votes
1answer
116 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, \...
3
votes
0answers
56 views

skew Schur identity

Let $\lambda$ be a partition of size at least 2, and let $n>0$ be an integer. Prove that $$s_{\lambda/(1)}.h_{n}=\sum_{\lambda^{+}\supseteq \lambda\\\lambda^{+}/\lambda\ \text{hor.} \ n\ \text{...
3
votes
0answers
68 views

Question on Vertex Labeling (Related to Lucky Labeling of Graphs)

Suppose that for any bipartite planar graph $G=(V,E)$, we can find a vertex labeling $c:V\to \{1,2,3\}$ such that for any two adjacent vertices $u$ and $w$: $$c(u)-\sum_{v\in N(u)}c(v)\neq c(w)-\sum_{...
3
votes
0answers
49 views

Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces

Show that the number of monic irreducible polynomials of degree $n$ over a finite field of size $q$ is the same as the number of primitive necklaces of size $n$ with $q$ colors. I have the formula $$...
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 ...
3
votes
0answers
60 views

What do you get when you pull the Bruhat Decomposition back to the Lie algebra via the exponential map?

If $G$ is a connected, reductive, complex group with Borel subgroup $B < G$ and Weyl group $W$, we can write $$G = \bigsqcup_{w \in W} B w B$$ If $\mathfrak{g}$ is the Lie algebra of $G$, we have ...
2
votes
1answer
76 views

To show two formal power series equal

I am wondering whether the following two formal power series are equal: $A(x)=\Pi_{k=1}^{\infty}\frac{1}{1-x^{2k-1}}$, $B(x)=\Pi_{k=1}^{\infty}(1+x^k)$.
2
votes
2answers
279 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 ...
2
votes
2answers
760 views

A Variation of the even-town odd-town problem

Let assume facebook has $n$ users. Mark Zuckerberg decided that people are allowed to open groups under the following restrictions: 1) No two different groups can exactly the same participants. ...
2
votes
1answer
454 views

Number of permutations of $[n]$ with a multiple of $n$ inversions

We have a permutation $\left(a_1,a_2,...,a_n\right)$ of the set $\{1,2,...,n\}$. A pair $(a_i,a_j)$ is said to be an inversion of this permutation if $i<j$ and $a_i>a_j$. Find the number of ...
2
votes
2answers
111 views

Proof that the Lascoux-Schützenberger involutions satisfies the braid-relations

I am interested in the Lascoux-Schützenbereger involutions $\theta_i$, defined on semistandard Young tableaux. See this paper for definitions, page 4. These involutions satisfy the braid relations: (...
2
votes
2answers
151 views

Paths must cross in Lindström-Gessel-Viennot on the lattice

The following question (which I am going to answer myself) serves to close a little gap in some combinatorial proofs that use the Lindström--Gessel--Viennot lemma. Namely, I will show a little lemma, ...
2
votes
1answer
127 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 ...