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
4
votes
0answers
232 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+...
0
votes
0answers
37 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 ...
-2
votes
1answer
41 views

Painting balls with four colors

Suppose I have $n$ distinguishable balls and I want to paint them in four colors: red, blue, green, and yellow. How many ways of painting are there with odd numbers of red balls and odd number of blue ...
3
votes
0answers
68 views

Has anyone found this formula before?

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(\...
2
votes
1answer
33 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 ...
0
votes
0answers
33 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,...
3
votes
1answer
126 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 ...
3
votes
1answer
41 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 $\{...
4
votes
0answers
38 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 \...
8
votes
1answer
498 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 ...
0
votes
0answers
24 views

Schur function in linerly shifted power symmetric basis

Previously I have aksed the following question about schur function in power symmetric basis Schur function principal specialisation Let $s_{\lambda}(p_1,p_2,)$ denote schur function in power-sum ...
6
votes
0answers
60 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 $...
3
votes
1answer
86 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 ...
1
vote
2answers
33 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/...
5
votes
1answer
180 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 ...
4
votes
0answers
69 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. ...
1
vote
1answer
52 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^{\...
11
votes
2answers
133 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 ...
2
votes
2answers
40 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 ...
1
vote
3answers
107 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 $...
0
votes
0answers
40 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_{\...
0
votes
0answers
13 views

Linear Representations of a Commutative Association Scheme through Valencies

In section 2.5 of Bannai and Ito’s Algebraic Combinatorics 1 is the following claim: Let $(X,\lbrace R_i \rbrace_{i=0}^d)$ be a commutative association scheme with adjacency matrices $I=A_0,A_1,\ldots,...
0
votes
1answer
35 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 ...
2
votes
1answer
68 views

Binary Matrices and Similarity

Consider the space of square matrices $\mathcal{B}$ which take entries from $\{0,1\}$. I would like to find orthogonal matrices $Q$ such that, for a matrix $B \in \mathcal{B}$, the matrix $Q^TBQ \in \...
1
vote
0answers
63 views

On the number of facets of subcomplexes of Shellable simplicial complex

Let $\Delta$ be an abstract simplicial complex (https://en.wikipedia.org/wiki/Abstract_simplicial_complex) which is pure (i.e. all facets have same cardinality) and of dimension $d-1\ge 0$ and is ...
3
votes
1answer
283 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 ...
0
votes
4answers
60 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
49 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
73 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
51 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
43 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
29 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
57 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
669 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
32 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
81 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 ...
1
vote
0answers
34 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
26 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
326 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
116 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
93 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
96 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
58 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
107 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
64 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
48 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
2answers
77 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
50 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 ...
6
votes
4answers
177 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
49 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 ...