# Tagged Questions

**1**

vote

**0**answers

28 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 ...

**1**

vote

**0**answers

126 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 ...

**11**

votes

**0**answers

226 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 ...

**3**

votes

**1**answer

285 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

112 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 ...

**2**

votes

**1**answer

88 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 ...

**1**

vote

**0**answers

47 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, ...

**5**

votes

**3**answers

285 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 ...

**4**

votes

**1**answer

216 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 ...

**5**

votes

**0**answers

110 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 ...

**-2**

votes

**1**answer

99 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

265 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

68 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{ ...

**5**

votes

**0**answers

108 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

125 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 ...

**5**

votes

**2**answers

277 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 ...

**2**

votes

**0**answers

86 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 ...

**7**

votes

**1**answer

347 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 ...

**6**

votes

**1**answer

223 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

**1**answer

91 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 ...

**4**

votes

**1**answer

267 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 ...

**8**

votes

**3**answers

293 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 ...

**2**

votes

**0**answers

128 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 ...

**10**

votes

**3**answers

380 views

### Is a distributive lattice planar iff it admits no B3 sublattice?

A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the ...

**3**

votes

**0**answers

78 views

### Efficiently computing (plethysm-like?)substitutions of symmetric functions

This is a rather technical question, it arose in connection of some calculations that I need to have better grasp of the question Formal group law over $\mathbb{F}_p$ and my own older one What is ...

**2**

votes

**1**answer

94 views

### Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...

**5**

votes

**2**answers

161 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 ...

**4**

votes

**1**answer

108 views

### Countable hypo-hamiltonian graph

If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path.
Is ...

**4**

votes

**1**answer

206 views

### Counting couples of square-free polynomials over finite fields

I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$:
$$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\
y_2^2=h_2(t) ...

**3**

votes

**2**answers

202 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

73 views

### Exact growth rate of Longest Increasing Subsequence expectation

Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that ...

**3**

votes

**1**answer

251 views

### How many hamiltonian paths can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways you can arrange 5 people sitting around a round table so that the people sitting to the left of any person are ...

**0**

votes

**1**answer

66 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**3**

votes

**3**answers

84 views

### Block error-correcting codes over inhomogeneous alphabets

For $n := (n_1,\dots,n_N) \in \mathbb{N}_{>1}^N$, let $X_n := \prod_{j=1}^N [n_j]$, where as usual $[m] := \{1,\dots,m\}$.
Are there any known generic constructions for (Hamming) sphere ...

**5**

votes

**1**answer

159 views

### English translation of Witt's paper on the Mathieu groups?

Does anyone know of an English (or French) translation of Witt's paper Die 5-fach transitiven Gruppen von Mathieu ? (It's the one in which the Witt design is introduced. Well, I guess.)
Here's an ...

**2**

votes

**1**answer

107 views

### Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, ...

**1**

vote

**0**answers

122 views

### Counting number of ways to place bags and marbles inside bags so all bags contain an odd number of marbles

There was a famous trick question posed once in math.stackexchange here. The question can be loosely translated to "Is it possible to place nine marbles into four bags so that each bag has an odd ...

**6**

votes

**1**answer

194 views

### A combinatorial identity generalizing identity (3.111) from Gould's book

I am trying to prove the following identity, which I am sure is correct:
$$
\sum_{m=0}^{K}(-1)^m{n \choose m}{(n-m)r-1 \choose n-1}=1,
$$
where $K:=\left[n\frac{r-1}{r}\right]$ for some integer $r$, ...

**3**

votes

**1**answer

262 views

### Number of semi-standard tableau

What is the number of semi-standard tableau (weakly increasing on rows and strictly increasing on columns) for the partition $2n=n+n$ with entries $\{1,2, \cdots ,n\}$ such that each $i$ appears ...

**0**

votes

**1**answer

125 views

### Number of squares in a grid under certain conditions

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.
$A(n):$ # of squares with vertices on the grid.
It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = ...

**3**

votes

**3**answers

362 views

### Waring problem for binomial coefficients (generalization of Gauss' Eureka Theorem)

Is there a number k such that every natural number can be written as $\sum_{i=1}^k \binom{a_i}{3}$ for some natural numbers $a_i$'s?

**1**

vote

**0**answers

89 views

### Occupancy problem with limited capacity and two types of balls [closed]

I am considering the following problem that I suspect to be standard.
One has a set of $N$ balls composed of a fraction $\alpha$ of red balls and $(1-\alpha)$ of black balls (we assume $\alpha N$ is ...

**3**

votes

**0**answers

218 views

### Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...

**3**

votes

**0**answers

68 views

### Where does this identity involving sums of Hankel-like determinants over partitions come from?

For a partition $\lambda=( \lambda_1,\dots,\lambda_n)\vdash n$ with $\lambda_1\ge\dots\ge\lambda_n\ge0$ and any function $f:\mathbb Z\to\mathbb C$, define a Hankel-like $n\times n$ matrix ...

**11**

votes

**0**answers

301 views

### Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...

**12**

votes

**0**answers

250 views

### Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...

**4**

votes

**0**answers

56 views

### Is every planar point set be projections of vertices of a neighborly 4-polytope?

More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ be vertices of a neighborly polytope.
This problem comes from a simple ...

**5**

votes

**1**answer

108 views

### Beraha numbers and zeros of the chromatic polynomial of planar graphs

Question: What is the largest Beraha number known to be an accumulation point of real zeros of the chromatic polynomial of planar graphs?
Background:
The Beraha numbers $B_n=2+2cos(2\pi/n), ...

**1**

vote

**0**answers

118 views

### counting how many boxes from a given Young tableau contribute to hook length made out of two YTs

Think of a Young diagram as a collection of rows with numbers of elements
$\mu_1 \geq \mu_2 \geq \cdots \geq \mu_d \geq \mu_{d+1}=0$ (and $\mu_k=0$ for $k>d$) and define for $s=(i,j)$ (where $i$ ...

**10**

votes

**1**answer

273 views

### Dynamics of RSK

There is a way of viewing the RSK correspondence as a map (in fact, bijection) $A \overset{RSK}\longrightarrow \widehat{A}$ from $n\times n$ matrices with entries $\mathbb{N}$ to (weak) reverse plane ...