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)

1
vote
1answer
23 views

Method to construct a bipartite graph G' with 2n vertices from a graph G

I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup ...
3
votes
0answers
30 views

A lower bound for orthogonal partial circulant matrices

Let us call an $m$ by $n$ matrix with $m<n$ a partial circulant matrix it is the first $m$ rows of some square circulant matrix. Consider partial circulant matrices whose elements are either $-1$ ...
3
votes
2answers
43 views

Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form: $$\sum_{n=1}^k ...
2
votes
0answers
36 views

Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices

I'll give two equivalent statements of the setup, then give my questions. Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in ...
0
votes
0answers
46 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
-4
votes
0answers
92 views

Are polls good approximations [on hold]

Let $X$ be a finite set and $A\subseteq X$ and $m$ be a natural number satisfying $m\le |X|$ and $\epsilon$ be a small positive number. I'm interested to know if one selects a random $Y\subseteq X$ ...
1
vote
1answer
47 views

approximate diameter of polytopes in high dimensions

I just came across the following problem: Let us consider the unit corner of the n-cube $$ \Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 ...
7
votes
2answers
168 views

Repeats of all binary strings of length k

The question seems like it should be known, but I was not able to find it anywhere. How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ ...
1
vote
0answers
69 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 ...
-2
votes
0answers
116 views

Flower Arrangements [closed]

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 ...
16
votes
0answers
505 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 ...
10
votes
1answer
216 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, ...
4
votes
0answers
73 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}$$ ...
6
votes
0answers
85 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 ...
5
votes
0answers
159 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 ...
29
votes
2answers
849 views

The coupon collector's earworm

[EDITED mostly to report on the answer by Kevin Costello (and to improve the gp code at the end)] I thank Nicolas Dupont for the following question (and for permission to disseminate it further): ...
12
votes
1answer
224 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 ...
0
votes
0answers
73 views

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

Does anyone know a simplicial complex which is collapsible but there exist a subdivision of it which does not?
-2
votes
1answer
171 views

patitions of the number n [closed]

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 ...
1
vote
1answer
128 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 ...
3
votes
0answers
81 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 ...
0
votes
0answers
34 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 ...
1
vote
1answer
94 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 ...
5
votes
2answers
191 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} ...
2
votes
2answers
87 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 ...
9
votes
3answers
344 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$ ...
3
votes
0answers
221 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
1answer
160 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?
7
votes
0answers
136 views

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
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, ...
1
vote
1answer
66 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 ...
4
votes
1answer
185 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 ...
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 ...
4
votes
0answers
106 views

A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back. $N=1$ is standard coupon ...
2
votes
0answers
241 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 ...
12
votes
1answer
795 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 ...
53
votes
46answers
7k 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 ...
17
votes
0answers
397 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 ...
16
votes
1answer
235 views

Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others

What are known estimates for maximal $M$ for which their exists subsets $A_1,\dots,A_M$ in $\{1,\dots,n\}$ such that there do not exist different indexes $i,j,k$ for which $A_i\subset A_j\cup A_k$? ...
21
votes
5answers
736 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 ...
5
votes
1answer
377 views

Is every polynomial a factor of a trinomial?

We say that $T(X) \in \mathbb{Q}[X]$ is a trinomial if there exist $A,B,C \in \mathbb{Q}$ such that $T(X) = AX^n + BX^m + C$ for some $n \geq m \in \mathbb{N}$. Is it true that for each ...
4
votes
0answers
51 views

shifted symmetric power sums

The functions $p^*_k(x)=\sum_{i=1}^N ((x_i-i)^k-(-i)^k)$ are analogues of power sum symmetric functions, called shifted symmetric by Okounkov and Olshanski. Define ...
12
votes
1answer
407 views

Maximal Number of Pairs of Orthogonal vectors in a set of $n$ vectors in $\mathbb{R}^3$

Suppose you are given a set of $n$ non-zero vectors in $\mathbb{R}^3$. What is the maximum number of pairs of them that are orthogonal? The current guess is $\le 2n$. EDIT: I forgot to add that no ...
2
votes
0answers
88 views

What kinds of complexes can be collapsed to?

A simplicial complex $S$ is collapsible if there is a sequence of elementary collapses that bring $S$ down to a single point; I'll denote this as $S \searrow \{pt\}$. I am wondering about a similar ...
5
votes
0answers
107 views

Minimal possible cardinality of a $(a_1, …, a_k)$-distributable multiset

Suppose we have a multiset $M$ of positive rational numbers. Sum of $M$ equals $1$. We'll call this multiset $n$-distributable for some $n\in \mathbb{N}$, if there exists a partition $M_1 \sqcup ... ...
0
votes
0answers
66 views

Ways to color a string with a fixed number of boundaries

Number of ways to color a string of $N$ objects with $M$ colors ($M<N$) so that there are $N_i$ objects of each color $i$ ($i=1,...,M$) and $k$ boundaries. The values of $\{N_i\}_i$ are fixed and ...
4
votes
2answers
272 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 ...
5
votes
0answers
69 views

Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
2
votes
0answers
115 views

How distributive are the bad Laver tables?

Suppose that $n\in\omega\setminus\{0\}$. Then define $(S_{n},*)$ to be the algebra where $S_{n}=\{1,...,n\}$ and $*$ is the unique operation on $S_{n}$ where $n*x=x$ $x*1=x+1\,\text{mod}\, n$ and if ...
0
votes
1answer
74 views

Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...