Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

6
votes
1answer
140 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
3
votes
0answers
93 views

Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
5
votes
1answer
281 views

Infinite sequence avoiding a countable set of words

As an application in group theory, I would need an infinite sequence over a finite alphabet, that avoids a sequence of words $w_i$, where the length of $w_i$ is such that $l(w_i) > 10^8 ...
3
votes
3answers
318 views

Aperiodic graphs

The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph ...
6
votes
0answers
122 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 ...
1
vote
0answers
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
0answers
121 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
0answers
170 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
1answer
280 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
0answers
108 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
1answer
85 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
0answers
45 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
3answers
273 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
1answer
210 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
0answers
108 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
1answer
97 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
1answer
263 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
1answer
61 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
0answers
104 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
1answer
123 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
2answers
266 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
0answers
80 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
1answer
343 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
1answer
209 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 ...
2
votes
1answer
85 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
1answer
228 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
3answers
275 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
0answers
124 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
3answers
377 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
0answers
74 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
1answer
84 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
2answers
154 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
1answer
107 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
1answer
202 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
2answers
198 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
0answers
72 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
1answer
237 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
1answer
61 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
3answers
82 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
1answer
156 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
1answer
101 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
0answers
121 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
1answer
190 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
1answer
259 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
1answer
106 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
3answers
356 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
0answers
86 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
0answers
213 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
0answers
62 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 ...
10
votes
0answers
287 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 ...