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)

-3
votes
0answers
70 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 ...
14
votes
0answers
373 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 ...
2
votes
0answers
52 views

Finding combintorial 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
53 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
70 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
131 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 ...
23
votes
2answers
376 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 ...
11
votes
1answer
195 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
66 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?
-2
votes
1answer
160 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 ...
3
votes
1answer
123 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 ...
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 ...
0
votes
0answers
31 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
89 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
177 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
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 ...
9
votes
3answers
340 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
216 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
154 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
114 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
0answers
52 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
62 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 ...
-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 ...
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 ...
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
80 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
234 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 ...
11
votes
1answer
691 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 ...
50
votes
37answers
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 ...
17
votes
0answers
381 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
231 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
723 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
372 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
48 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
402 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
86 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
105 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
64 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
267 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
68 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
114 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 ...
1
vote
0answers
14 views

Properties of Optimal k-Tour Spanners

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$. I would like ...
10
votes
3answers
443 views

Self-Similar Graphs

Many fractals can be generated using and infinite sequence of graphs. For example, Sierpinski's Gasket could be generated by the following sequence of graphs. Many definitions of fractal dimensions ...
5
votes
2answers
342 views

What is the permutation group generated by those three given morphisms of the affine space $\mathbb{F}_q^3$?

Let $\mathbb{A}^3 = \mathbb{F}_q^3$. Consider the following three functions $\mathbb{A}^3\to\mathbb{A}^3$: \begin{eqnarray*} h: (x, y, z) &\mapsto& (x, y, xy - z) \\ u: (x, y, z) ...
18
votes
1answer
402 views

Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...
0
votes
0answers
56 views

Is there a general theory for the structure of the (semi)group generated by morphisms of an affine space $F_p^3$?

Consider an affine space $\mathbb{F}_p^3$, and assume we have a handful of morphisms $f_i : \mathbb{F}_p^3 \rightarrow \mathbb{F}_p^3$ given by $$f_i(x, y, z) =(P_i(x, y, z), Q_i(x, y, z), R_i(x, y, ...
2
votes
0answers
27 views

s-arc transitivity and the Moore bound

Given a vertex $x$ of a graph, call the subgraph induced by all vertices of distance $\le n$ from $x$ the $n$-neighbourhood of $x$, denoted $N_n(x)$. Let $G$ be a regular graph of diameter $n+1$. For ...
3
votes
0answers
61 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
13
votes
2answers
973 views

Is there a $q$-L'Hospital's Rule?

Let $\binom{n}{j}_q$ be a $q$-binomial coefficient and $(x;q)_n = (1-x)(1-qx)\cdots(1-q^{n-1}x).$ Consider the sum $$f(n,m,r,k)= \sum\limits_{j = 0}^{2n} {( - 1)}^{ j}q^{mj^2+rj} ...