**0**

votes

**0**answers

5 views

### Hypergraphs that can be represented by simply closed curves respecting edge intersection

Good evening. Hypergraphs can be drawn by representing each vertex as a point in the plane and each hyperedge as a closed curve that contains the points corresponding to the vertices that belong to ...

**9**

votes

**3**answers

2k views

### Two questions about combinatorics journals

Hello,
I have two questions regarding combinatorics journals. I hope that this is the right place for such questions.
Which combinatorics/DM journals would you consider as the "top tier"?
I tried ...

**2**

votes

**1**answer

110 views

### Rank changes with matrix edits

Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric).
Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix.
Case $1$: $M+W\in\{0,1\}^{n\times n}$.
Could ...

**27**

votes

**2**answers

2k views

### Projective Plane of Order 12

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...

**4**

votes

**0**answers

72 views

### Asymptotics of the multipartition function

Recall that the multipartition function $p_k(n)$ counts the number of $k$-tuples of partitions $\lambda^1,\ldots,\lambda^k$ of numbers $a_1,\ldots,a_k$ with $a_1+\cdots+a_k=n$. It has a generating ...

**0**

votes

**1**answer

135 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**-2**

votes

**0**answers

79 views

### A modified notion of ranks

Given $M\in\{0,1\}^{n\times n}$ of rank $r$.
Denote
$p^{\Bbb Z_{\geq0}}=\{p^t:t\in\Bbb N\cup\{0\},\quad p\text{ a prime}\}$.
$\mathscr{P}_r[M,p]=\{P\in\{0,p^{\Bbb Z_{\geq0}}\}^{n\times ...

**0**

votes

**1**answer

116 views

### The weighting function for the infinite product of necklaces

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$ where $N(n,a)$ is the number of fixed necklaces of length $n$ composed of $a$ types of beads.
Let's rewrite the product in a way ...

**5**

votes

**3**answers

227 views

### A balls and urns model for a hashing problem

Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c ...

**0**

votes

**0**answers

82 views

### Combinatorial support set in CRT

Is there a function $g(s)$ such that if there is a set of numbers $\{r_i\}_{i=1}^m$ such that $r_i\bmod p_j\in\{0,1\}$ at every prime in $\{p_j\}_{j=1}^n$ such that $2^t\bmod p_j\neq1$ at every ...

**3**

votes

**1**answer

251 views

### Balancing real numbers in one dimension

Given numbers $0 \leq d_i \leq 1$ for $i=1,\ldots,m$, it is easy to see that you can always find signs $\varepsilon_i \in \{-1,1\}$ such that the partial sums $\sum_{i=1}^k \varepsilon_i d_i/2$, for ...

**4**

votes

**0**answers

88 views

### Staircase Schur functions squared

Let $\Delta_n$ be the staircase-shaped partition $(n-1,n-2,\dots,1)$. Are there any non-obvious combinatorial objects that index $s_{\Delta_n}^2$? Here, $s_\lambda$ is the Schur function indexed by ...

**1**

vote

**0**answers

27 views

### Constructing pointwise-or independent binary matrices

Let $M$ be an $m \times n$ matrix such that every $M_{ij} \in \{0,1\}$.
We say that $M$ is `$\lor$-irreducible' if (i) no row is a pointwise-or of other rows, and (ii) no column is a pointwise-or of ...

**10**

votes

**2**answers

369 views

### Inequalities for averaging over partially ordered sets

Let's start from a classical inequality:
If $0\le a_1\le\cdots\le a_k$ and $0\le b_1\le\cdots\le b_k$ then
$(a_1+\cdots+a_k)(b_1+\cdots+b_k)\le k(a_1b_1+\cdots+a_k b_k)$.
It can be written also in ...

**7**

votes

**1**answer

97 views

### Covering a set with images of a transversal

Let $G$ be a permutation group on a finite set $\Omega$ with orbits $\Omega_1,\ldots,\Omega_k$.
By a transversal we mean a set $\lbrace\omega_1,\ldots,\omega_k\rbrace$ with $\omega_j\in\Omega_j$ for ...

**1**

vote

**0**answers

103 views

### Experimentation with partial Euler products

Richard Mathar $[1]\& [2]$ shows that
\begin{align}
&\zeta_{2}(s)\equiv\prod_{\Omega(n)=2}^{}\left(\dfrac{1}{1 - n^{s}}\right)^{-1}=\exp \left(\sum _{k=1}^n \frac{P(k s)^2+P(2 k s)}{2 ...

**3**

votes

**1**answer

109 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**8**

votes

**0**answers

106 views

### Maximizing the number of semistandard Young tableaux

Is anything known about the following question? Given a positive
integer $p$ and a real number $0<\alpha<1$, what partition $\lambda$
whose parts sum to $\alpha p^2$ (asymptotically) and whose ...

**2**

votes

**1**answer

76 views

### Relationship of clique, independence, and chromatic numbers

For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...

**5**

votes

**1**answer

378 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**1**answer

262 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**1**

vote

**0**answers

40 views

### Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...

**3**

votes

**1**answer

282 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**7**

votes

**1**answer

348 views

### Which finite groups are not the automorphism group of some rooted finite tree?

The question is as given in the title:
Which finite groups are not the automorphism group of some rooted finite tree?
A rephrasing could be: Is any finite group representable as the automorphism ...

**4**

votes

**1**answer

182 views

### Decomposing $(\mathbb C^n)^{\otimes m}$ as a representation of $S_n\times S_m$

$V=\mathbb C^n$ is a $\mathbb CS_n$-module, where $S_n$ is the symmetric group of degree $n$, via the representation sending a permutation to the corresponding permutation matrix. The tensor power ...

**0**

votes

**0**answers

36 views

### Property of summations [on hold]

Suppose to have the following identity:
$$
\sum_{i=i_0}^{i_1}\sum_{j=j_0}^{j_1} f(i,j) = \sum_{i=i_0}^{i_1}\sum_{j=j_0}^{j_1} f(i,j)g(i,j),
$$
for 'good' indexes $i,j$ and some functions $f,g$.
What ...

**-1**

votes

**0**answers

41 views

### Combinatorics: Identical objects and distinct groups [on hold]

I'm confused between the following 2 formulae:
1) Number of ways to put n identical objects into r distinct boxes, such that the ordering is NOT important is:
(n+ r - 1) C r
2) Number of ways to ...

**6**

votes

**1**answer

334 views

### Categorifying the free monoid and non-commutative generating functions

I am a complete novice in the art of categorification, so this may not be a great question.
Background. The groupoid $\mathbf {FSet}$ of finite sets and bijections categorifies the natural numbers ...

**5**

votes

**0**answers

97 views

### How do you categorify the cycle index series?

Let $F$ be a combinatorial species. The exponential generating series of $F$ is defined to be
$$ \sum_{n \geq 0} \frac{ \lvert F_n \lvert x^n}{n!} $$
It was observed by Baez and Dolan in their paper ...

**17**

votes

**0**answers

464 views

### Combinatorics of Quantum Schubert Polynomials

Let $S_n$ be the symmetric group. Let $s_i$ denote the adjacent transposition $(i \ i+1)$. For any permutation $w\in S_n$, an expression $w=s_{i_1}s_{i_2}\cdots s_{i_p}$ of minimal possible length is ...

**-2**

votes

**1**answer

93 views

### Combinatorical meaning of such expression [closed]

Any combinatorical meaning or interpretation of
$$1^{\alpha_1}2^{\alpha_2}3^{\alpha_3}...s^{\alpha_s}\alpha_1!\alpha_2!...\alpha_s!$$
for partition ...

**6**

votes

**1**answer

257 views

### Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)

Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v_0$, $v_1$, ..., $v_{k-1}$ and exactly $k$ arcs $v_0 ...

**1**

vote

**1**answer

154 views

### Term for number of crossings of smooth curves

Two smooth oriented finite curves $g_1, g_2$ on e.g. the 2-dimensional torus can intersect each other transversally in two ways: either the pair $(Tg_1(x),Tg_2(x))$ of tangent vectors in the ...

**4**

votes

**3**answers

256 views

### Perimeter/Neighborhood of a graph on grid

Hello,
I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one.
Now I want to claim ...

**15**

votes

**1**answer

905 views

### Singmaster's conjecture

Has any work been done on Singmaster's conjecture since Singmaster's work?
The conjecture says there is a finite upper bound on how many times a number other than 1 can occur as a binomial ...

**5**

votes

**0**answers

97 views

### Intersections of the B-orbits and the orbits of some other Borel subgroups in the flag variety G/B

This is a follow-up of this previous question below:
Intersections of $B$ and $B^-$ orbits in the flag variety $G/B$
Let $G = SL_n(\mathbb{C})$, $B$ be the standard Borel subgroup, and consider some ...

**2**

votes

**1**answer

116 views

### Existence of Steiner system designs given $n,k,t$

I am familiar with the recent Keevash paper here which proves that given some $t,n,k,\lambda$ then provided standard divisibility conditions hold, and $n$ is suitably large, there exists a ...

**1**

vote

**1**answer

57 views

### Hadwiger-Nelson problem in higher dimensions

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by
$V(\text{HN}_n) = \mathbb{R}^n$;
$E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...

**2**

votes

**0**answers

76 views

### Adding a row to a Young Tableau via Novelli-Pak-Stoyanovskii

Let $T_{\lambda}$ be the set of standard young tableaux (SYT) of shape $\lambda_1\geq \lambda_2\cdots\geq \lambda_n$. Now consider pushing a row $\mu$ with $\mu\geq \lambda_1$ onto $Y$ to give shape ...

**4**

votes

**1**answer

194 views

### The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...

**58**

votes

**3**answers

4k views

### What is the amplituhedron?

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...

**7**

votes

**1**answer

336 views

### Quest for a human proof of a $q-$binomial identity

Let $$f(n,k) = \sum\limits_{j = - k}^k {{{( - 1)}^{k - j}}}
\binom{n-j}{k-j}\binom{n+j}{k+j}.$$
Then $f(n,k)=\binom{n}{k}$
because it satisfies $f(n,k)=f(n-1,k)+f(n-1,k-1)$ and the obvious ...

**5**

votes

**2**answers

253 views

### Combinatorial designs textbook recommendation

Good evening, I am currently taking a class which has combinatorial designs as the first topic, we are using Peter Cameron's book Designs, Graphs, Codes and their Links which I am finding extremely ...

**6**

votes

**1**answer

193 views

### A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.
What is $\chi(G)$?
(This is a variant of the ...

**3**

votes

**2**answers

191 views

### Picking codewords that are close

I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...

**2**

votes

**0**answers

120 views

### Ticket lottery — distributing $n$ tickets among $N$ people fairly

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend ...

**3**

votes

**1**answer

320 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**2**

votes

**1**answer

82 views

### Minimal family of k-sets containing all t-sets

Let $n \ge k \ge t \in \mathbb{N}$, and consider a universe $U$ of size $n$. Let $\mathcal{F}$ be a family of $k$-subsets of $U$, such that every $t$-subset of $U$ is contained in at least one member ...

**8**

votes

**3**answers

269 views

### Distinguishing combinatorial maps by their linearizations

Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k ...

**5**

votes

**2**answers

148 views

### Number of Dyck paths with prescribed number of edges

I am trying to find a formula for the trace of certain matrix. To do that I was forced to determine the number of Dyck paths with prescribed number of edges.
By a Dyck path I mean a lattice path from ...