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)

0
votes
0answers
58 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 l(w_{i-1})$. ...
2
votes
1answer
232 views

Name search for special Linear Integer Program

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
1
vote
0answers
47 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 ...
9
votes
3answers
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
1answer
111 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
2answers
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 ...
5
votes
0answers
78 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
1answer
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 ...
0
votes
1answer
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
3answers
232 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
0answers
87 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
1answer
253 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
89 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
0answers
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
2answers
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
1answer
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
0answers
104 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
1answer
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
0answers
109 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
1answer
78 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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
350 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
1answer
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
0answers
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
0answers
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
1answer
335 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
0answers
99 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
0answers
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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
2answers
254 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
1answer
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
2answers
192 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
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
1answer
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
1answer
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
3answers
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 ...