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)

11
votes
0answers
301 views

Does Langton's ant cover every n by 6 gridded torus?

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus. For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...
8
votes
0answers
155 views

What's the analogue of a Young symmetrizer in the Brauer algebra?

According to Schur--Weyl duality, the centralizer of $\mathrm{GL}(V)$ acting diagonally on $V^{\otimes N}$ is the group algebra of the symmetric group $\mathbb S_N$. An equivalent formulation is the ...
1
vote
0answers
131 views

Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before. For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...
5
votes
1answer
159 views

The Maximal $\ell_2$ norm of a signed sum of vectors

Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors: $$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$ where $s_j$'s can only take values of $+1$ or $-1.$ I ...
1
vote
1answer
137 views

How many finite subsets in $\mathbb{Z}^d$ have a given sum of squares?

Let $|\cdot|$ denote the usual norm in $\mathbb{Z}^d$. Given a finite subset $S \subset \mathbb{Z}^d$, let $\varphi(S) = \sum_{z \in S}|z|^2$. Given $m \in \mathbb{N}$, what is the size of ...
3
votes
0answers
83 views

Looking for a natural definition of certain polynomials associated with skew Young diagrams

Consider a connected skew Young diagram in the English notation and then rotate it counterclockwise by $\pi/4$. This rotation can be avoided by simply replacing "rows" by "diagonals" in the below, but ...
0
votes
0answers
137 views

Generating function for reciprocals of Stirling numbers?

Is there an (ordinary or exponential) generating function for the reciprocals $\frac{1}{s(n,k)}$ of the Stirling numbers of the first kind? Also, is there some general way to find generating ...
3
votes
0answers
63 views

Which (polytopal) fans/polytopes are secondary?

Let $P$ be a (d-1)-dimensional polytope with $n$ vertices that sits in an affine hyperplane in $\mathbb{R}^d$. The secondary fan of $P$ is a polytopal fan in $\mathbb{R}^n$ with $d$-dimensional ...
0
votes
0answers
86 views

Adjacency graph of a polyomino

Given a polyomino, the "adjacency graph" has one vertex for each tile and an edge connecting tiles which are adjacent (diagonal doesn't count). Is anything known about which graphs can be the ...
19
votes
0answers
444 views

Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows: Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel ...
16
votes
0answers
234 views

Deforming a basis of a polynomial ring

The ring $Symm$ of symmetric functions in infinitely many variables is well-known to be a polynomial ring in the elementary symmetric functions, and has a $\mathbb Z$-basis of Schur functions ...
9
votes
5answers
691 views

Combinatorial\Probabilistic Proof of Stirling's Approximation

Stirling's approximation is the following well-known asymptotic result: $$n! \approx \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}$$ This result has several analytical proofs, for example via Laplace's ...
14
votes
1answer
673 views

In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?

This question is a variation of the return to the origin problem. Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = ...
8
votes
1answer
218 views

Yet another Erdős–Szekeres game

Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$ The player after whose turn there is a monotone subsequence of length $n$ loses. I guess that the question 'who wins' ...
8
votes
1answer
472 views

Erdős-Szekeres game

Given $n$. Two players in turn mark points on the plane. No three may be collinear, no $n$ may form a convex $n$-gon. The player who does not have legal move loses. Who has a winning strategy?
11
votes
1answer
471 views

Continuous functions and 2-bushy trees

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison. A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...
0
votes
1answer
91 views

A particular argument in the review on expanders by Hoory-Linial-Wigderson

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Can someone explain what is the argument there which seems to conclude ...
4
votes
1answer
489 views

How to prove this identity on double summation series?

I suspect the following identity is valid, but I can not prove it. I just calculate it numerically. ...
1
vote
1answer
178 views

Asymptotic of a certain double sum involving binomial coefficients

Consider sums of the form $S(n)=\sum^{n}_{m=0}\sum^{m}_{k=1}2^{2k+m+1}{n-m+k+1 \choose 2k+2}{m \choose k}$ I am interested in the asymptotics of $S(n)$ as $n\to \infty$. More precisely I would ...
7
votes
1answer
186 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
110 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
292 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
327 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
153 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
31 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
132 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
235 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
290 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 ...
5
votes
0answers
161 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
93 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
49 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
295 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
219 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
116 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
100 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
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
1answer
70 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
110 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
130 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
288 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
89 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
350 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
232 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
1answer
98 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
292 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
295 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
129 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
395 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
82 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
95 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 ...