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
2 views

An identity related to partitions into $n$ parts and Schur polynomials

While working with Schur polynomials I found what seems like a nice identity, and I wonder if it has a simple proof. Notation: Suppose $d,n\in\mathbb{N}$, and $\lambda =(\lambda_1,\dots,\lambda_n)$ ...
2
votes
2answers
128 views

Combinatorial identity involving number of cycles (of any length) in a permutation

I am going through Phil Hanlon's paper and on page 127, right after the first paragraph, "It is well known that.." which boils down to the following identity: $$ \prod_{i=0}^{n-1}(\beta-i) = \sum_{\...
6
votes
1answer
234 views

The current status of the conjecture on algebraic matroids

Can anyone point out some articles for the conjecture: the dual of an algebraic matroid is algebraic? Thank you!
0
votes
0answers
63 views

Sum of unit vectors always has a binary span after constrained permutations

Conjecture: Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$. An enumeration $ E \cup -E = \{f_1, \ldots, ...
6
votes
0answers
137 views

A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
-1
votes
1answer
128 views

number of partitions from 0 to n^2 [on hold]

You are given the numbers 0 to n^2. You must use n numbers with no number greater than n to form all the partitions of the numbers 0 to n^2. For example with n=4 you want to find the partitions of 7:...
0
votes
1answer
48 views

Count Functional digraph [on hold]

Given a set of nodes, how can I count the number of different functional digraph containing a specific number of connected components? With a restriction that no node can have an edge point to itself. ...
-2
votes
0answers
23 views
2
votes
0answers
46 views

Average range of Motzkin path

Motzkin path are paths from (0,0) to (n,0) in $\mathbb{Z}^2$ such that we are allowed to move SE, E and NE. More on this is here https://en.wikipedia.org/wiki/Motzkin_number I would like to know if ...
6
votes
1answer
120 views

q-analog of a combinatorial identity involving binomial coefficients

Using, e.g., properties of iterated finite differences it is easy to show that for any pair of integers $n$ and $m$ with $n>\!>m$ one has the identity $$ \sum_{k=0}^m(-1)^{k-m} {n-k\choose m}{m\...
2
votes
2answers
173 views

Examples of Sets with Positive Upper Density

While reading the statement of Roth's theorem I started asking myself what are examples of sets of positive upper density? It's not hard to come up with a few: Flip a coin with probability $\mathbb{...
6
votes
1answer
126 views

On a result of Frankl and Wilson

In the paper 'Intersection theorems with geometric consequences' (Combinatorica 1981) P. Frankl and R. M. Wilson consider families $\mathcal{F}$ of $k$-subsets of $\{1,\dots,n\}$ with the restriction ...
1
vote
1answer
127 views

Rank 2 complex vector bundles over $S^2\times S^2$

How could people classify all rank $2$ complex vector bundles over $S^2\times S^2$ up to isomorphism? Could you give a rank 2 complex vector bundle which cannot be split as a sum of two line bundles?
4
votes
0answers
86 views

A color interpolation lemma

I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof. Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...
5
votes
0answers
93 views

For which Ramsey type results density versions are wrong?

I look for examples of Ramsey-type statements, for which the density counterparts do not hold. Example: usual Ramsey theorem. If all edges of a complete graph $K_n$ are colored in $c$ colors, there ...
0
votes
0answers
47 views

When are these sums consecutive integers? [closed]

It is possible to construct $\frac{n(n-1)}{2}$ sums which each contain two distinct summands chosen from a set $n$ numbers. For which $n\geq 3$ do there exist a set of $n$ (distinct) integers such ...
3
votes
0answers
98 views

A question about smooth convex lattice polygons

Let $P$ be a smooth convex lattice polygon in $\mathbb{R}^2$ (the lattice being $\mathbb{Z}^2$). Here smooth means that at any vertex of $P$, the two primitive integer vectors (i.e. vectors whose ...
3
votes
0answers
88 views

The number of monotone Boolean functions

In the paper "The number of monotone Boolean functions" A. D. Korshunov calculates an asymptotic number of the number of monotone Boolean functions (see https://en.wikipedia.org/wiki/Dedekind_number)...
3
votes
0answers
64 views

Minimal algebraic degree of symmetric unit distance embedding of Heawood graph

I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
4
votes
0answers
76 views

Random polyominoes containing $2\times2$ squares

The construction quoted in the question "How to sample a uniform random polyomino?" claims to produce a "uniform random polyomino". But apart from the mentioned possibility of getting stuck, it also ...
0
votes
1answer
35 views

What is the shatter coefficient / VC - dimension of some hypothesis set?

Let $H:=\{h:\mathbb{N}_0^n \rightarrow \{0,1\}| h(x_1,\cdots,x_n) = \mathbb{1}_0(\sum_{i\in I}{x_i}-\sum_{j \notin I}{x_j}) \text{ for some } I \subset \{1,\cdots,n\}\}$ where $\mathbb{1}$ is the ...
0
votes
1answer
63 views

On some examples of critical families

I'm reading the book on Injective choice functions by Holz, Podewski and Steffens, and I find it to be at the same time well written and quite difficult. It has almost no examples - and in quite a few ...
10
votes
3answers
286 views

How to sample a uniform random polyomino?

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
0
votes
0answers
70 views

Variation on stones in buckets

This is a spinoff, see Collecting stones in n buckets. Frankly speaking my only motivation is that I became curious: what happens if one redistributes the stones into the same buckets? More ...
0
votes
0answers
43 views

How many different solutions does this cube puzzle have?

I designed a 4x4x4 soma cube in AutoCad and then built it with wood cubes. Now I want to know how many different solutions there are for it. Similar to the Bedlam Cube, there are twelve pentacube and ...
0
votes
1answer
258 views

How many subsets I of $\{1,\cdots,n\}$ exist?

How many subsets $I$ of $S:=\{1,\cdots,n\}$ exist such that $\sum_{i \in I} x_i \neq \sum_{j \in S-I} x_j$ for all $0 < x_1 < \cdots < x_n$? Let $b_n$ be this number. Then we are ...
3
votes
0answers
190 views

On weight enumerators of codes

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
4
votes
0answers
86 views

Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
3
votes
1answer
132 views

A Combinatorial Identity Involving Characters of $S_n$ (Reference Request?)

It is a well-known exercise that $C_n = \chi_{(n,n)}(1)=\chi_{(n,n)}^{1^n}$ where $C_n$ is the $n$th Catalan number and $\chi_{(n,n)}^{1^n}$ is the character of the irrep $(n,n)$ on conjugacy class $1^...
1
vote
0answers
113 views

Singular Locus of a Schubert variety

I am trying to compute the singular locus of the schubert variety $X_w$ in $G_{2,7}$ where $w=(4,7) \in I_{2,7}$. Following the notation in the book "The Grassmannian Variety: Geometric and ...
5
votes
2answers
177 views
+150

Seeking very regular $\mathbb Q$-acyclic complexes

This question was raised from a project with Nati Linial and Yuval Peled We are seeking a $3$-dimensional simplicial complex $K$ on $12$ vertices with the following properties a) $K$ has a complete $...
0
votes
0answers
47 views

Solving Recursive Expression for Counting Unrooted Tree Topologies

The book Bayesian Evolutionary Analysis with BEAST by Alexei J. Drummond et al. (2015) states at section 2.2.1 that the number of rooted unlabelled (binary) tree topologies $a_n$ is given by the ...
2
votes
0answers
79 views

Bounding Schur polynomials of a particular shape

Consider Schur polynomials $s_\lambda$ with $\lambda = (2m, m, m, \ldots, m, 0)$ and $\ell(\lambda) = n$ (that is, $\lambda$ has $n$ rows). Here $m \gg n$, which, for the sake of concreteness, let's ...
2
votes
0answers
57 views

Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$. Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
0
votes
0answers
118 views

Counting integer solutions for a system of (in)equalities [migrated]

I wish to enumerate the number of solutions of the system of equations and inequalities for 3 non-negative integer unknowns $x,y,z \ge 0$: ($a$,$b$ specified) \begin{align} x+y+z&=a\\ x+y&>...
1
vote
1answer
199 views

Approximation of sets

Is the following true? For every $\varepsilon>0$ there is a finite subset $W$ of $\mathbb{N}\times \mathbb{N}\times \mathbb{N}$, such that $$|p_1(W)\cap p_2(W)\cap \{p_1(x)+p_2(x):x\in W\}\cap \{...
2
votes
2answers
257 views

Convergence issues with infinite product of formal series

Question first: Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have $$ P(x) \equiv \prod_{j=1}^\infty (1 -...
24
votes
1answer
515 views

Inequality for hook numbers in Young diagrams

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$, define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...
-1
votes
1answer
40 views

Size of smallest set in critical covering of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ...
7
votes
1answer
148 views

Does an expander remain an expander after removing few vertices and edges?

Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices. Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
2
votes
0answers
191 views

Average minimum number of random k-sparse vectors in $\mathbb{F}_2^n$ to span a specific base vector?

A while back I posted a question in MO about the average minimum number of independent random k-sparse (having at most $k$ non-zero elements) vectors belonging to $\mathbb{F}_2^n$ to span the whole ...
8
votes
1answer
148 views

How many edges can be added to two circles before the graph becomes Hamiltonian?

Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way ...
4
votes
1answer
382 views

Three dimensional representations of Alternating group

The alternating group $A_5$ has $2$ irreducible representation of degree $3$. The characters for these representations have irrational values. I guess the ring of invariants of these representations ...
1
vote
1answer
180 views

An extremal problem on matrices

Is it possible to determine (or give bounds for) the following extremal problem: Let $k,m,r$ be positive integers such that $k,m \geq r$. What is the least number $n$ such that for any $r \times n$ ...
3
votes
1answer
81 views

Probability of collision of some family of hash functions

Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
0
votes
1answer
84 views

Critical coverings of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ...
0
votes
0answers
181 views

Number Theory and p-Power-Partitioned Numbers

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, we're going to define its digits-partition as the next set $D_{N} = \bigcup_{j=1}^{n}\bigcup_{k=1}^{p(a_{j})}\{(P_{k},j)\}$, where each pair $(...
-3
votes
1answer
106 views

Arranging blue and red balls in a circle [closed]

Suppose we have $b$ identical blue balls and $r$ identical red balls. How many ways are there to arrange them in a circle? Clearly, if we wanted to arrange the balls in a row, the answer would have ...
1
vote
1answer
320 views

On Sylvester's coin problem for geometric progressions

Given $a,b\in\Bbb N$ we know from http://www.emis.ams.org/journals/INTEGERS/papers/i33/i33.pdf that the smallest number that cannot be written as a non-negative linear combination of integers with ...
6
votes
0answers
100 views

On the use of Weisfeiler-Leman refinement in Babai's GI proof

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...