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
4answers
40 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 ...
0
votes
1answer
30 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 ...
0
votes
0answers
26 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$ ...
2
votes
1answer
28 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 ...
0
votes
1answer
25 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 ...
0
votes
0answers
28 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 ...
3
votes
1answer
47 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 ...
1
vote
1answer
171 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 ...
1
vote
0answers
17 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 ...
0
votes
0answers
32 views

Number for ways to arrange 10 distinct object into 4 distinct boxes

What is the number of ways to arrange 10 distinct objects into 4 distinct boxes, where each box hold no more than 4 objects This question was asked earlier today, but has been deleted, I don't know ...
0
votes
0answers
17 views

Cramer's Theorem in Ellenberg's and Gijswijt's bound for the cap set theorem

The paper I am referring to is https://arxiv.org/pdf/1605.09223.pdf, page 3, which I am doing for my undergraduate research problem. I understand most of the paper and have been able to fill in the ...
1
vote
0answers
31 views

On subsets of $\mathbb N^2$ with elements not comparable w.r.t. componentwise order

Let $\mathbb N$ denote the set of nonnegative integers . For $(a,b);(c,d)\in \mathbb N^2$, define $(a,b)\le (c,d)$ iff $a\le c$ and $b\le d$. Let us call call a subset $S\subseteq \mathbb N^2$ to ...
1
vote
0answers
25 views

Postnikov's Lemma 16.3 in TOTAL POSITIVITY, GRASSMANNIANS, AND NETWORKS

Paper linked here: https://math.mit.edu/~apost/papers/tpgrass.pdf I'm having trouble parsing the proof of Lemma 16.3, perhaps because I only have first-principles-level familiarity with matroids. I ...
0
votes
1answer
95 views

Computing a rook polynomial

I have this $3\times 3$ square above, where the $5$ white squares form a board $B$, and I am trying to calculating the rook polynomial of $B$, using the following formula : the answer is given as $...
2
votes
1answer
109 views

On a particular kind of simplicial complex with maximum facet size of $3$.

Let $\Delta$ be an abstract simplicial complex on $n$ vertices such that $\max \{|F| : F$ is a face of $\Delta \}=3$. Let $f_2$ be the number of faces of size (cardinality) $3$ and $f_1$ be the ...
0
votes
1answer
82 views

Is there generalization of the natural numbers?

Natural numbers are defined inductively https://softwarefoundations.cis.upenn.edu/lf-current/Basics.html#lab30 as s(s(...s(0)...)). Such definition is nothing special, especially when one can ...
3
votes
0answers
92 views

Combinatorial bijection of primitive factorization

Let $\nu$ is a partition on $n$. Given a $n$ cycle $(1,2,\ldots,n)\in S_n$. Let define $H_g^{m}((n);\mu)$ count the number of tuples $(\tau_1,\ldots,\tau_r)$ in symmetric group $S_n$.Let $\beta$ ...
2
votes
1answer
56 views

On finding a finite set of generators for a certain semigroup

Let $A$ be a finite subset of $\mathbb Z^2$. Let $\mathbb ZA$ be the subgroup of $\mathbb Z^2$ generated by $A$. Let $\mathbb R_{+}, \mathbb Q_{+}$ denote the set of non-negative real and rational ...
6
votes
2answers
99 views

A collection of sets that cover all edges in Kn?

The problem is the following: Let $\mathcal{F}$ be a family of distinct proper subsets of {1,2,...,n}. Suppose that for every $1\leq i\neq j\leq n$ there is a unique member of $\mathcal{F}$ that ...
2
votes
0answers
45 views

Symmetric matrix with 0 diagonal, each row (and column) being a permutation on $n-1$ symbols.

Let $n$ denote a positive integer, and consider the set $S$ of $n\times n$ symmetric matrices with zero diagonal (denoted $A$) so that for each $j$, $a_{ij}$ ($i=1,2,\dots,n)$ is a permutation of $0,1,...
0
votes
0answers
42 views

Counting covered pairs of integer partitions

I am trying to solve a problem in algebric combinatorics, where i want to prove that for integers $m,n$ and pairs ($\lambda$ , $\mu$) of integer partitions with a maximum of $m$ non zero parts which ...
0
votes
0answers
46 views

Central factorial number

I have the following expression the numbers which are called central factorial numbers $$T(a,b)= 2 \sum_{j={0}}^{b}(-1)^{b-j} \frac{j^{2a}}{(b-j)!(b+j)!}$$ I am not clearly getting their ...
0
votes
0answers
35 views

Cauchy product on exponential generating functions combinatorial proof

I have this fact: Given two exponential generating functions $A(x)$ and $B(x)$ where $A(x)=\sum_{k\ge0}A_k\frac{x^k}{k1}$ and $B(x)=\sum_{l\ge0}B_l\frac{x^k}{l!}$ we can deduce the product to be: $$...
0
votes
2answers
69 views

Combinatorics in a $n \times n$ grid

Natural number $n>2018$ is given. Numbers $1,2,\ldots,n^2$ are written (in an arbitrary order) into the fields of the $n\times n$ grid. Prove that it is possible to choose $n$ fields so that there'...
1
vote
0answers
40 views

Combinatorial proof of the identity relating Hurwitz numbers

Let define $H^{m}((n);\mu)$ count the number of tuples $(\alpha,\tau_1,\ldots,\tau_r ,\beta)$ in symmetric group $S_n$ where $\alpha$ is fixed cycle of type $(n)$ and $\beta$ cycle of type $\mu$ and ...
0
votes
0answers
88 views

Combinatorial bijective proof equality

Let define $H^{m}((n);\mu)$ count the number of tuples $(\alpha,\tau_1,\ldots,\tau_r ,\beta)$ in symmetric group $S_n$ where $\alpha$ is fixed cycle of type $(n)$ and $\beta$ cycle of type $\mu$ and ...
6
votes
4answers
155 views

Algebraic proof of a combinatoric question (Combinatoric proof is given)

I had a IMO training about double counting. Then, there is a problem which I hope there is a combinatoric proof. Here comes the problem: For every positive integer $n$, let $f\left(n\right)$ be ...
4
votes
0answers
47 views

Plethysm with Basis?

For any partition $\lambda$ we denote by $S_\lambda$ the corresponding Schur functor. Now consider $\textrm{GL}(\mathbb{C}^n)$ with its natural action on $\mathbb{C}^n$. Using character theory, one ...
2
votes
1answer
119 views

Find the closed form of $\sum\limits_{k=0}^n \frac{1}{n\choose k}$: Incomplete Beta function in a combinatoric question

Recently I asked a question about the sum of $\sum_{k=0}^n {n\choose k}^p f\left(k\right)$. Then, I was thinking of the case when $p=-1, f\left(x\right)=1$, which is $\sum_{k=0}^n \dfrac{1}{n\choose k}...
4
votes
1answer
464 views

Equality like Pascal triangle

I have noticed the following is true. Let's denote the equation below as (1) $$\sum_{k=1}^{d+1}(-1)^{d+1-k}\frac{1}{(d+1)(k-1)!(d+1-k)!}\prod_{i=1}^{d+1}\Big(\frac{q}{h}+(k-i)\Big)\prod_{j=k}^{d}\Big(...
1
vote
0answers
46 views

A doubt in the proof of Combinatorial nullstellensatz

(Combinatorial Nullstellensatz I) Let $f\in \mathbb{F[x_1,x_2\ldots x_n]}$, and let $S_1,S_2\ldots S_n$ be non empty subsets of $\mathbb{F}$. If $f(x)=0$ for all $x\in S_1\times S_2\times \ldots S_n$,...
0
votes
0answers
49 views

Coefficient of a finite sum and positivity

I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$ $$\bar{S}(k)=\...
2
votes
1answer
59 views

$n$-derivative of $m$-power of function

There is well-known Leibniz rule generalization for the $n$-th derivative of product of $m$ functions $f_1, f_2, \ldots, f_m$, namely: $$ D^n(f_1 f_2 \cdots f_m)=\sum_{k_1+k_2+\cdots+k_m=n} \binom{n}{...
0
votes
0answers
78 views

Crystal operators

Define the operator $s_i$ on tableaux: Consider letters $i$ and $i + 1$ in row reading word of the tableau. Successively “bracket” pairs of the form (i + 1, I ). Left with word of the form $i^r (i +...
3
votes
0answers
79 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{...
0
votes
3answers
521 views

Number of permutations with all cycles of even length

For even $n$ (only!), let $e_n$ stand for the number of permutations with all cycle of even length. Let $E(x)$ be the exponential generating functions. Prove that $E(x) = (1 - x^2)^{-\frac12}.$ I ...
3
votes
1answer
102 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.$$ ...
0
votes
2answers
52 views

Combinatorial problem discrete math

Find the no of ways of placing 6 identical balls into 3 distinct boxes in such a way that first box contains 0,1 or 2 objects,2bd box contains 1,2,3 objects and 3rd one contains 3 or 5 objects. Ans- ...
0
votes
1answer
74 views

Convergence of Exponential Generating Functions

In page 10 of "Enumerative Combinatorics by Stanley, volume 2", let $h(n)=2^{n \choose 2}$ be the number of graphs on an $n$-element vertex set $S$. And let $c(n)$ be the number of connected graphs on ...
0
votes
1answer
36 views

Citation/Reference for this Formula [closed]

Does anyone know any sources that could possibly be used as a citation of some form of the formula below? $$\sum_{n=0}^{k} (a+n)(b-n) = (k+1)ab + \frac{k(k+1)}{2}(b-a)+\frac{k(k+1)(2k+1)}{6}$$
2
votes
1answer
102 views

We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.

We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree. Idea: Let $M$ be an adjacency matrix and work all over field $\mathbb{Z}_2$. Then if $M$ ...
2
votes
0answers
39 views

Chromatic Polynomial of Circulant Graph with Two Parameters

It is easy to get the Chromatic-Polynomial of a Circulant-Graph of size $n$ with one parameter $P[C_{n}(i),x]$. Is there a way to get an explicit formula for the chromatic polynomial of a circulant ...
3
votes
0answers
86 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
62 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 $$...
1
vote
1answer
188 views

Vishnoi's Proof of Combinatorial Nullstellensatz

The question was already asked here: Question regarding a proof of the Combinatorial Nullstellensatz, but I am having trouble understanding the document in the comment, and so I was wondering if ...
1
vote
2answers
119 views

Applying Burnside's lemma to show there are $k+n-1 \choose k-1$ ways to store n stars in k bins?

Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and ...
7
votes
3answers
271 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 ...
2
votes
2answers
157 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
0answers
64 views

Hook-length formula [closed]

Let $\lambda=(\lambda_1,\ldots,\lambda_n)$ be a partition of $d$. Then hook length formula gives us $$dim(\lambda)=\chi_{1^d}^{\lambda}=\frac{d!}{\prod h_{\lambda}(i,j)}$$ where $\chi_{a}^{b}$ denote ...
10
votes
1answer
375 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) ...