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
0 answers
16 views

Hyperplane arrangement : The Shi arrangement

I have been lately reading Hyperplane arrangement lectures by Richard Stanley on https://www.cis.upenn.edu/~cis610/sp06stanley.pdf . In lecture 5, Theorem 5.16 we define the characteristic polynomial ...
user avatar
0 votes
0 answers
7 views

For the Boolean Algebra of the subsets of $F_p^n$ find number of elements of rank $k$.

Given some "power" (that is, repeated direct products) of a finite abelian group, such as $$\mathbb{Z}_2^2=\{(0,0),(0,1),(1,0),(1,1)\}. $$ What is the number of subgroups of rank $k$. I ...
user avatar
2 votes
0 answers
40 views

Common divisor of Gaussian coefficient expressions

I have a question about common divisors of some expressions involving Gaussian coefficients, in particular in the case ${n \brack 1}_{q} = \frac{q^{n}-1}{q-1}$ where $q$ is a prime power. It is well ...
user avatar
5 votes
0 answers
45 views

Are reflection subgroups corresponding to closed root subsystems always parabolic?

In the third paragraph of this reference, the following is stated: let $W$ be a Coxeter group with set of roots $R$, and let $H$ be a subgroup of $W$ generated by reflections (i.e. by conjugates of ...
user avatar
  • 828
0 votes
1 answer
64 views

generating function of finite sum involving $\left(\!\!\binom{n}{k}\!\!\right)$

Notation: $$ \left(\!\! \binom{n}{k}\!\!\right)={n+k-1 \choose k}=\frac{(n+k-1)!}{k!(n-1)!} $$ where $n!$ is the factorial, i.e. $1\cdot 2\cdots n.$ Let $n,N\in \mathbb{Z}_{>0}.$ I'm stuck at ...
user avatar
0 votes
0 answers
26 views

Binomial coefficient identities from h-vector of a simplicity complex. [duplicate]

My question is to show the below equality $$\sum_{j=0}^{d}(-1)^{j}\binom{d}{j}\binom{d-j}{i}=0$$ when $d>i \geq 0$ for any integers $d,i$. This inequality is came from Stanley's note. Given an $f$-...
user avatar
  • 1,595
1 vote
1 answer
46 views

Operations with Circulant Matrix using GAP

I am newbie using GAP software. I need to know how to use GAP software for algebraic computations with circulant matrix. Some examples would suffice. Just for clarity Circulant Matrix: In linear ...
user avatar
  • 19
14 votes
3 answers
255 views

Family of sets with $|F_i| \equiv 2\pmod 3$ and $|F_i \cap F_j| \equiv 0 \pmod 3$

Let $p$ be a prime. By considering the incidence vectors of subsets $F_1,\ldots,F_m$ of $\{1,2,\ldots,n\}$, such that $|F_i| = a \not\equiv 0 \pmod p$ and $|F_i \cap F_j| \equiv 0 \pmod p$ for all $1\...
user avatar
  • 2,547
0 votes
0 answers
27 views

Symmetric function in power-sum basis

The following is a symmetric function $$\prod_{i=1}^{m}(1-x_{i}z)^{-u}\prod_{j=1}^{m}(1-y_{i}z)^{-v} \prod_{i=1}^{m}\prod_{j=1}^{n}(1-(x_i +y_j)z)^{-w}\tag{*}$$ where $u,v,w$ are positive integers. in ...
user avatar
  • 968
0 votes
0 answers
55 views

Hilbert series of $\mathbb Q[x_1,...,x_n]/I_\Delta+(x_1^2,...,x_n^2)$ , for Stanley-Reisner ideal $I_\Delta$

Let $\Delta$ be an abstract simplicial complex on vertex set $\{x_1,...,x_n\}$, fix the field $\mathbb Q$ and let $I_{\Delta}$ be the Stanley-Reisner ideal of $\mathbb Q[x_1,...,x_n]$ , and $\mathbb Q[...
user avatar
0 votes
1 answer
45 views

Minimum value of factorial multiplication

I studied that if x + y + z = 3n (i.e if value of x+y+z is some fixed number which is multiple of 3) then minimum value of x!y!z! is when x=y=z. How can we prove this statement? Attempt: Well, I ...
user avatar
1 vote
0 answers
12 views

Change of coordinate and Linear Ode

Let $G(z)$ be a rational function. So if we have a series $$S(x):=\sum_{n}a_n x^n $$ where $$ a_n = \prod_{i=1}^{n}G((i-1)h) $$ We can conclude that the series satisfies a Linear differential ...
user avatar
  • 968
3 votes
0 answers
57 views

Representation for the Bose-Mesner algebra and its dual.

If you are familiar with the algebra, just skip the following brief introduction, that is fine. In the study of Bose-Mesner algebra. We know given that the commutative association scheme $\mathfrak{X}...
user avatar
  • 1,396
2 votes
0 answers
50 views

The Schwartz genus of a fibration

I'm working on the topological complexity of a path connected space, which is a particular case of the sectional category (or the Schwartz genus), but all the articles refer to an other article named &...
user avatar
1 vote
2 answers
74 views

change of summation, Hermite polynomial formula from generating functions

Now given the exponential generating function of the Hermite polynomial $$e^{ux-(1/2)u^2} = 1+\sum_{n=1}^\infty \dfrac{u^n}{n!}h_n(x),$$how do I derive the closed form formula of the Hermite ...
user avatar
  • 315
1 vote
1 answer
65 views

Cycle indicator symmetric function and Polya's theorem

Let $G$ be a subgroup of the symmetric group $S_n$. Given a partition $\lambda$ of $n$, denote by $n_G(\lambda)$ the number of elements in $G$ of cycle-type $\lambda$. The cycle indicator function of $...
user avatar
  • 1,865
2 votes
1 answer
110 views

Operate an aviation network without condition: Each city has a direct flight to 3 other cities; There is always a flight visiting all cities once each

Problem. A country has $10$ cities. Operate an aviation network within $2$ following conditions: a. Each city has a direct flight to exactly $3$ other cities. b. From a beginning city, there is always ...
user avatar
3 votes
0 answers
58 views

Is the poset of all subsets of a collection of sets rank-unimodal?

I'm working on Richard P. Stanley's Algebraic Combinatorics and have been stuck on this problem for a while: Let $S_1, S_2,..., S_{k}$ be finite sets with $\#S_1 = \#S_2 = ... = \#S_{k}$. Let $P$ be ...
user avatar
  • 114
0 votes
1 answer
190 views

Prove or disprove that there exists no more specific match-ups involving these 4 third-placed teams for the round of 16 other than

UEFA EURO 2020 has been just started, still with the format of 24 teams. The top 2 in each groups will proceed to the round of 16 along with the best of 4/6 third-placed finishers. Prove or disprove ...
user avatar
5 votes
0 answers
332 views

Suppose we have $n$ points in a plane, not all on the same line. Then they are determining at least $n$ different lines.

Suppose we have $n$ points in a plane, not all on the same line. Then they are determining at least $n$ different lines. Suppose points $T_1,...,T_n$ determine $m$ lines $$\ell_i(x,y) :\;\;a_ix+b_iy+...
user avatar
  • 86.2k
0 votes
0 answers
53 views

Reference Request: Introduction to Gelfand-Tsetlin Patterns

I'm looking for a source that gives a good introductory exposition to Gelfand-Tsetlin patterns and their related combinatorics. Most expository sources seem to introduce GT patterns when and how they ...
user avatar
5 votes
1 answer
122 views

Has anyone found this formula before? [closed]

I found this formula. \begin{equation} \sum_{\lambda \vdash n}\frac{2^{l(\lambda)}}{z_{\lambda}}=n+1 \end{equation} where $\lambda \vdash n$ means that $\lambda$ is an integer partition of $n$, $l(\...
user avatar
1 vote
1 answer
39 views

On the dimension of an abstract simplicial complex built from minimal vertex covers of a finite simple graph

Let $G$ be a finite simple graph on a vertex set $\{x_1,...,x_n\}.$ Let us call a vertex cover of $G$ to be minimal if none of its proper subset is a vertex cover. Let $C_1,...,C_h$ be the collection ...
user avatar
  • 1,200
0 votes
0 answers
46 views

Hall Scalar product calculation: $\langle h_3p_6, s_{(5,4)}\rangle$

This is a problem from an old qualifying exam I am reviewing: Calculate: $\langle h_3p_6, s_{(5,4)}\rangle$ where $\langle \cdot,\cdot \rangle$ is the Hall scalar product defined by $\langle s_\lambda,...
user avatar
3 votes
1 answer
260 views

Infinite product of infinite sums of formal power series: proof?

Teaching a course on algebraic combinatorics has made me aware of a technical fact about formal power series that is used throughout the subject, but that I have never seen formally stated, let alone ...
user avatar
3 votes
1 answer
51 views

Prove that the Following Graph Has $p F^2_p$ Spanning Trees

I am working on Algebraic Combinatorics by Richard P. Stanley. Problem 4 on Chapter 9 reads: Let $p \ge 5$, and let $G_p$ be the graph on the vertex set $\mathbb{Z}_p$ with edges $\{i, i+1 \}$ and $\{...
user avatar
  • 452
4 votes
0 answers
66 views

Generalized Hertzsprung Problem

The Hertzsprung Problem goes as follows: In how many can we place exactly $n$ non-attacking kings on a $n \times n$ chessboard such that there is exactly $1$ king in each row and column where $n \in \...
user avatar
8 votes
1 answer
513 views

Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$. Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$.

Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$. Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$. Proof: Let $P_0:= \{11,22,...,99\}$ and for $i= 1,2,...49$ and $11\nmid i$ make ...
user avatar
  • 86.2k
6 votes
0 answers
70 views

Proving that a group is either cyclic or not-simple

This problem is from Chapter 7 of Algebraic Combinatorics by Richard p. Stanley: Let $X$ be a finite set, and let $G$ be a subgroup of the symmetric group, $S_X$. Suppose that the number of orbits of $...
user avatar
  • 452
4 votes
2 answers
202 views

Normalization of an affine toric variety is toric

In the book "Toric Varieties" by Cox-Little-Schenck, Proposition 1.3.8 is left as an exercise. It essentially characterizes what the normalization of an affine toric variety is. The ...
user avatar
1 vote
2 answers
57 views

Is every abstract simplicial complex the independence complex of a simple graph?

Given a simple (no loops, no multi-edges) undirected graph $G$ on $n$-vertices, one can assign an abstract simplicial complex known as the independence complex (https://en.m.wikipedia.org/wiki/...
user avatar
  • 1,200
4 votes
1 answer
202 views

Why does Alon's combinatorial Nullstellensatz require working over a field.

In Alon's Nullstellensatz theorems (theorems 1.1 and 1.2 here) why is it necessary for $F$ to be a field? As far as I can tell, all the arguments in the proofs should work when $F$ is, say, an ...
user avatar
  • 299
8 votes
0 answers
144 views

Clubs whose intersections are multiples of six (Oddtown variant)

This is a question about generalizing the famous "Clubs in Oddtown" problem. The original setup is that a town has $n$ people, and $m$ clubs each consisting of a subset of the population. ...
user avatar
  • 56.8k
1 vote
1 answer
89 views

Help with an expression of the Schur polynomial

I am reading: https://www2.math.upenn.edu/~peal/polynomials/schur.htm where it says: The Schur polynomial is defined as $$s_\lambda(x_1,...,x_n)=\prod_{1\le i<j\le n}(x_i-x_j)^{-1}\det(x_j^{\...
user avatar
  • 5,185
11 votes
2 answers
295 views

Intuition behind picking group actions and Sylow

A common strategy in group theory for proving results/solving problems is to find a clever group action. You take the group you are interested in (or perhaps a subgroup), and find some special set ...
user avatar
  • 8,497
2 votes
2 answers
53 views

In a primitive symmetric association scheme, why does $E_j$ occur in some power of $E_i$ for each $i,j$?

I am having some trouble in the proof of the Absolute Bound Condition for primitive symmetric association Schemes in the book Algebraic Combinatorics I by Bannai and Ito (Chapter 2, Section 4, Theorem ...
user avatar
  • 458
1 vote
3 answers
111 views

Orbit of a point under the action of the stabiliser of another point

I'm wondering, for a group $G$ acting on a set $X$, what can be said about the orbit of a point under the action of a stabiliser subgroup of $G$. Let $x\in X$ and let $H = {\rm Stab}_G(x)$. Obviously $...
user avatar
  • 1,295
0 votes
0 answers
42 views

One part power series annihilator

This following appear in infinite variable but for discussion let's take everything is finite if it makes the answer simpler. \begin{equation} \label{PartitionfuncKS} \mathcal{Z}^{KS}(x)=\sum_{\...
user avatar
  • 968
0 votes
1 answer
41 views

Merging polynomials together

Given the (monic) polynomials $P$ and $Q$, we can split them over an appropriate field into linear factors to write $P(x)=(x-a_1)\dotsb(x-a_m)$ and $Q(x)=(x-b_1)\dotsb(x-b_n)$, and then form the ...
user avatar
  • 4,453
1 vote
0 answers
86 views

On the number of facets of subcomplexes of Shellable simplicial complex

Let $\Delta$ be an abstract simplicial complex which is pure (i.e. all facets have same cardinality) of dimension $d-1\ge 0$ and is shellable, with a shelling order of the facets given by $F_1,...,F_m$...
user avatar
  • 129
4 votes
1 answer
331 views

Given a positive integer $n$, some straight lines and lattice points such... Prove that the number of the lines is at least $n(n+3)$.

Given a positive integer $n$ and some straight lines in the plane such that none of the lines passes through $(0,0)$, and such that every lattice point $(a,b)$, where $ 0\leq a,b\leq n$ are integers ...
user avatar
  • 86.2k
0 votes
4 answers
87 views

How many partitions of $n$ different objects into equinumerous parts are there?

How many partitions of $n$ distinct objects are there, given that all parts are equinumerous? (Let us not consider the empty partition and the identity partition.) The cases when $n$ is the unit, or ...
user avatar
  • 12.8k
0 votes
1 answer
70 views

On the geometric realization of a finite abstract simplicial complex which is connected, orientable $3$-manifold without boundary

Let $\Delta$ be an abstract simplicial complex on finitely many vertices and $|\Delta|$ be it's geometric realization. (https://en.m.wikipedia.org/wiki/Abstract_simplicial_complex) If $|\Delta|$ is ...
user avatar
  • 1,200
0 votes
0 answers
98 views

Decomposing into irreducible $S_n$ modules, aka Specht modules.

Let $S_{\pi}$ where $\pi$ is an integer partition of $n$, denote the Specht module corresponding to $\pi$. I am trying to decompose the set of all homogeneous polynomials in $x_1,x_2,...,x_n$ ...
user avatar
  • 2,551
2 votes
1 answer
92 views

Minimum distance of a code given its basis

I know that to determine the minimum distance of a code given its basis we can follow this procedure: Let $\{ c_1, \ldots, c_k \}$ be a basis for a code of length $n$ and dimension $k$. Then the ...
user avatar
  • 160
0 votes
1 answer
62 views

Strongly regular graphs with parameters $(v,k,0,3)$

I want to find all the srg with parameters $(v,k,0,3)$. I leave my work so far below: By the balloon equation we obtain that $v=\frac{k^2+2k}{3} + 1$. Suppose that $k \geq \frac{v}{2}$. Then $k \in ...
user avatar
  • 160
0 votes
0 answers
32 views

Graph with no triangles and with two non-neighbours vertices having exactly $b$ common neighbours is regular

I have encountered the following problem: If $\Gamma$ is a graph on at least $3$ vertices and containing no triangles and with two non-neighbours vertices having exactly $b \geq 2$ common neighbours ...
user avatar
  • 160
3 votes
1 answer
77 views

Proof of 3-perfect codes [duplicate]

I am reading a the proof of a theorem that says that $3$-perfect codes can only have length $7$ or $23$. I do not understand the following: It follows from the definition that if $n$ is the length of ...
user avatar
  • 160
1 vote
1 answer
990 views

Single file queue with people as blockers

In a single-file queue of $n$ people with distinct heights, define a blocker to be someone who is either taller than the person standing immediately behind them, or the last person in the queue. For ...
user avatar
  • 581
1 vote
0 answers
40 views

RSK and Matrices

It is well known that the RSK algorithm assigns to every square matrix with nonnegative integer entries a pair of semistandard Young Tableaux of same shape. The matrices are here used as just a square ...
user avatar
  • 543