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)

51
votes
39answers
6k views

Important formulas in Combinatorics

Motivation: The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
-2
votes
1answer
463 views

Conjugate vertices and distinguishing properties

Motivation (added) A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$. A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by ...
27
votes
3answers
629 views

The coupon collector's earworm

I thank Nicolas Dupont for the following question (and for permission to disseminate it further): I have a playlist with, say, $N$ pieces of music. While using the shuffle option (each such ...
6
votes
0answers
133 views

Nonattacking configurations of k bishops on an m by n rectangular board

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in ...
1
vote
0answers
43 views

What characteristic of a graph depend on the vertex labeling?

Different labeling on a graph produces class of isomorphic graphs. Two isomorphic graphs possess similar characteristic such as connectivity, degree distribution of vertices, equality of spectrum and ...
8
votes
0answers
132 views

Finding combinatorial models / statistics

In many cases in combinatorics and especially algebraic combinatorics with some representation theory, the main problem is about finding the correct statistic on a mathematical object. For example, ...
-2
votes
0answers
103 views

Flower Arrangements [on hold]

We have a $n\times m$ grid with $k$ flowers (not necessarily distinct). The grid is assumed to have horizontal and vertical symmetry. What is the value of $A(n,m,k)$, where $A(n,m,k)$ is the number of ...
12
votes
1answer
749 views
+100

A question about certain sets of permutations of the ordered pairs $(1,1),(1,2),\cdots,(1,n),\cdots,(n,1),(n,2),\cdots,(n,n)$

Let $n>1$ be a given positive integer. For any $0\leq k\leq n^2$, let $A_k$ be the set of permutations $((i_1,j_1),(i_2,j_2),\cdots,(i_{n^2},j_{n^2}))$ of the ordered pairs ...
15
votes
0answers
438 views

A Linear Order from AP Calculus

In teaching my calculus students about limits and function domination, we ran into the class of functions $$\Theta=\{x^\alpha (\ln{x})^\beta\}_{(\alpha,\beta)\in\mathbb{R}^2}$$ Suppose we say that ...
4
votes
0answers
59 views

“Edge Density” of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let $$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$ ...
11
votes
1answer
205 views

What is the maximum size of a set system where the intersection of any two incomparable members is not in the set?

Let the set $\mathcal{F}$ consist of subsets of $[n]$. Suppose that for any incomparable $A$ and $B$ in $\mathcal{F}$, we have $A \cap B \notin \mathcal{F}$. What is the largest possible size of ...
-2
votes
1answer
162 views

patitions of the number n [on hold]

I'm having difficult with the following question : A. Show that the number of partitions of n where in each one of them the even numbers appears at most once equals to the number of partitions of n ...
5
votes
1answer
382 views

Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way? Edited to add: For the benefit of illustration, here's a few face posets: the boundary of a ...
5
votes
0answers
137 views

Congruences involving binary forms and primes of the form $x^2+y^2$

Let $a_s$ be \begin{align*} a_s=\sum_{k=0}^s{s+k\choose k}2^k, \end{align*} which is the coefficient of $x^s$ in \begin{align*} \frac{3-\sqrt{1-8x}}{2(x+1)\sqrt{1-8x}}. \end{align*} ( see ...
6
votes
0answers
74 views

Recursions which define polynomials?

Let $k$ be a positive integer and let $$h(n,k,q)=\frac{1-(1+q^{k})q^{2k(n-1)+1}+q^{2}}{1-q^{2n-1}}h(n-1,k,q)-\frac{(1-q^{k(2n-3)})(1-q^{2k(n-1)})q^2}{(1-q^{2n-1})(1-q^{2n-3})}h(n-2,k,q)$$ with ...
10
votes
1answer
218 views

Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...
0
votes
0answers
68 views

A simplicial complex which is collapsible but there exist a subdivision of it does not [on hold]

Does anyone know a simplicial complex which is collapsible but there exist a subdivision of it which does not?
8
votes
3answers
600 views

Arithmetic product of symmetric functions: why is it integral?

For every commutative ring $A$, let $\mathbf{Symm}_A$ be the ring of symmetric functions over $A$. Let $\mathbf{Symm}$ without a subscript denote $\mathbf{Symm}_{\mathbb{Z}}$. We can define a ...
14
votes
8answers
50k views

The factorial of -1, -2, -3, …

Well, n! is for integer n < 0 not defined -- as yet. So the question is: How could a sensible generalization of the factorial for negative integers look like? Clearly a good generalization should ...
3
votes
1answer
124 views

Injective subset function

Let $X$ be a non-empty set and let $F: X \to {\cal P}(X)$ be a function with the following property: for $A \subseteq X$ we have $|A| \leq |\bigcup F(A)|$. Does this imply that there is an ...
5
votes
2answers
182 views

Dickson/determinant type polynomial (updated)

For $2\leq \ell \leq k$, consider the polynomial \begin{equation} P_{k,\ell} = \prod_{1\leq a_1+\ldots+a_k\leq \ell} (a_1x_1+\ldots + a_kx_k)\in \mathbb{F}_2[x_1,\ldots, x_k] \end{equation} ...
7
votes
0answers
121 views
+50

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously but despite asking on math.se and offering a bounty, no progress has been made. For a given positive integer $n$, consider all ...
1
vote
1answer
63 views

Maximum size of a union of incomparable chains

The following question was asked on math.stackexchange, where it received no answers. http://math.stackexchange.com/questions/1392669/maximum-size-of-a-union-of-incomparable-chains Let ...
3
votes
0answers
217 views

Existence of a block design

Let $\ell$ be an integer parameter. I want to ask the existence of the following design: There is a universal constant $\beta < 1$ such that for all sufficiently large $\ell$, the following holds: ...
2
votes
2answers
86 views

Relation between number of non-negative and positive integers points in simplices

I asked this question on math.SE before, but did get not get an answer. Therefore I hope it is ok to post it here on this site.. Let $q \in \mathbb{R}_+$ and $0 < w_1 \leq w_2 \leq \ldots w_d \in ...
1
vote
1answer
91 views

Number of binary sequences in which the number of $(1, 1)$ and $(0, 0)$ is prespecified

Consider a binary sequence $\mathbf{a}_n$ consisting of 1s and 0s. Let us denote by $f(\mathbf{a}_n)$ the number of $(1, 1)$ and $(0, 0)$ in $\mathbf{a}_n$; I am not sure whether there is a formal ...
2
votes
0answers
77 views

Combinatorial interpretation for a toric intersection number

Let $X$ be an $n$-dimensional toric variety and let $D$ be an effective divisor (eg nef or ample). Is there a combinatorial interpretation (eg in terms of the fan or polytope) of the intersection ...
43
votes
6answers
3k views

How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson. Theorem. Let ...
0
votes
0answers
32 views

Maximum norm of discrete Fourier transform [duplicate]

I have considerable numerical evidence that for all $0\leq k\leq{{n-1}\over 2}$ ($n$ odd) there exists a subset $ S_k$ of {1,2,...,n} of cardinality $k$ such that the modulus square of ...
20
votes
5answers
2k views

The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
8
votes
3answers
742 views

Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras? What I need from that ...
2
votes
1answer
202 views

Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...
15
votes
3answers
1k views

Rhombus tilings with more than three directions

The point of this question is to construct a list of references on the following subject: Fix vectors $v_1$, $v_2$, ..., $v_g$ in $\mathbb{R}^2$, all lying in a half plane in that cyclic order. I am ...
9
votes
3answers
342 views

Minimum size of the union of sets

I came accross this combinatorial problem in my computer science research. You are given a collection of k sets $S_1,...,S_k$ such that for any $i \neq j$, $ \vert S_i \setminus S_j \vert \geq p$ ...
14
votes
0answers
414 views

Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015] Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
2
votes
1answer
156 views

Schubert calculus and Pieri's formula

In the lecture notes Grassmannians: the first example of a moduli space. MIT Open Course Ware. page 7: Are there any formal publications (books/papers) where I can find the formula?
17
votes
0answers
383 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
10
votes
1answer
632 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}$, ...
1
vote
0answers
53 views

Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, ...
4
votes
2answers
162 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
6
votes
2answers
656 views

Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...
21
votes
5answers
725 views

How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question. For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...
4
votes
1answer
183 views

Smoothening a measure, II

There is an almost invisible, but significant difference between the question below and that recently answered by Boris Bukh. Given a probability measure $\mu$ supported on a finite set ...
4
votes
2answers
268 views

Categories of finite objects

In my experience, category theory is very successful at providing powerful machinery to reason about large objects or objects unrestricted in size, for example (logical) models (via accessible ...
2
votes
0answers
235 views

A variant frobenius problem

From Sylvester's theorem we know that using only coins of sizes $a,b$, we can change exactly $\frac{(a-1)(b-1)}2$ different big coins up to $(a-1)(b-1)$. Denote sets ...
-1
votes
0answers
51 views

bound on the size of a circuit [closed]

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
5
votes
1answer
188 views

a question on lattice invariants

Let $V$ be an $n$-dimensional vector space and $L$ be a lattice in $V$, i.e. a free $\mathbb{Z}$-module of full rank. Define the following two numbers. Let $\lambda$ be the minimal positive real ...
7
votes
1answer
616 views

Combinatorics of lattice walks with forbidden points

If I'm not in error, the number of walks on a 2-dimensional integer lattice of length 2n steps from the origin to a point (x,y) has a nice closed form: ${2n \choose n + (x + y)/2}{2n \choose n + (x - ...
1
vote
2answers
120 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 ...
2
votes
1answer
120 views

Smoothening a probability measure

Given a probability measure $\mu$ supported on a finite set $S\subset{\mathbb R}^2$, define $$ f(z):=\max\left\{\frac{\mu(x)+\mu(y)}2\colon \frac{x+y}2=z,\ x,y\in S \right\}, \ z\in{\mathbb ...