**0**

votes

**0**answers

3 views

### Additional condition to the Bollobas theorem in extremal set theory

The Bollobas'1965 theorem is the following:
If $A_1,...,A_n$ and $B_1,...,B_n$ are two sequences of subsets of $X=\{1,...,r\}$ such that $A_i\cap B_j = \emptyset$ if and only if $i=j$, then
...

**18**

votes

**2**answers

795 views

### A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I
state it in a different but equivalent form. Let $a(n)$ be the sequence
at http://oeis.org/A131868, that is,
$$ a(n) ...

**6**

votes

**3**answers

191 views

### Numerical invariants for a graph or its complement that are bounded by some constant

I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but ...

**6**

votes

**1**answer

169 views

### Exotic line arrangements

I would like to discuss about the following problem. Hopefully, you will suggest me some ideas and bibliography.
At first I provide some basic definitions to set up the notation.
Let us consider a ...

**1**

vote

**0**answers

88 views

### universality for large deviations?

This is a question about universality in probability theory, with combinatorics in mind.
Consider a sequence of polynomials $P_n$ in one variable, with positive coefficients. Combinatorics is a large ...

**2**

votes

**1**answer

129 views

### How many times does a simple symmetric random walk of length n return to the origin?

Consider the simple symmetric random walk on the integers starting from
the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as
$$ w:= \omega_0 \omega_1 \ldots ...

**9**

votes

**0**answers

294 views

### diameter as a Morse function

Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...

**5**

votes

**1**answer

98 views

### Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...

**15**

votes

**2**answers

1k views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**8**

votes

**0**answers

88 views

### A seemingly simple combinatorial object that must have an easy generating function

One more question related to my earlier "Special" meanders.
I am trying to isolate simplest problems related to it. Here is one.
For a composition (i. e. a tuple of natural numbers) ...

**4**

votes

**1**answer

258 views

### Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by
$(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers,
and $i=0,1,\dots,n+1$.
Does this simplex admit a regular, ...

**6**

votes

**1**answer

231 views

### Does $|A+A|$ concentrate near its mean?

Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...

**10**

votes

**1**answer

578 views

### Are there enough additive permutations?

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other ...

**1**

vote

**0**answers

51 views

### Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$

Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...

**-6**

votes

**0**answers

33 views

### Arrange numbers? [on hold]

hello the question i would like to ask is very difficult as english is not my native language so here it goes...I need a program or exel chart that arrange numbers in a group in order to get the ...

**3**

votes

**0**answers

139 views

### A generalization of Rogers-Ramanujan identity

The generalized Rogers-Ramanujan identity has the following form
$$\sum_{k_1\geq\cdots\geq k_r\geq 0}\frac{x^{k_1^2+\cdots +k_r^2+k_i+\cdots +k_r}}{(x)_{k_1-k_2}\cdots ...

**7**

votes

**2**answers

252 views

### Even parking functions and spanning trees of complete bipartite graphs

Set $\mathbb{N} := \{0,1,2,\ldots\}$. A parking function of length $n$ is a sequence $(\alpha_1,\ldots,\alpha_n) \in \mathbb{N}^n$ whose weakly increasing rearrangement $\alpha_{i_1} \leq \alpha_{i_2} ...

**7**

votes

**6**answers

841 views

### Binomial coefficient identity

It seems to be nontrivial (to me) to show that the following identity holds:
$$ \binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k} = 1. $$
This quantity is related to the volume of the ...

**5**

votes

**1**answer

182 views

### Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.
1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...

**7**

votes

**0**answers

61 views

### Factoring a multiset into a product of two multisets

Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that
$$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$
or ...

**0**

votes

**1**answer

61 views

### writing an integer as particular summation [on hold]

I think my question is an elementary question. Thanks for any help or comment.
Is there any formula for the number of writting a natural number $n$ in a summation as follows,
$n=a_1+\dots+a_k$, ...

**1**

vote

**0**answers

80 views

### Optimization on Binomial coefficients

Suppose we are given integers $1\leq r\leq N$, we want to study the following
$$
\max_{m_0+m_1=N,m_0,m_1\geq 1}\max_j \tbinom {m_0}{j}\tbinom {m_1}{r-j}.
$$
$N$ is very large, for instance $N\geq ...

**2**

votes

**1**answer

430 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...

**10**

votes

**2**answers

562 views

### What is the probability that two random permutations have the same order?

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...

**-5**

votes

**0**answers

52 views

### How many ways are there to order the numbers from 1 to 25 so that no primes occur consecutively? [on hold]

I just had this on an exam and was wondering if I answered it correctly. My solution was to first order the 16 composite numbers in this range, giving 17 spots to insert the 9 primes. So we have ...

**5**

votes

**2**answers

512 views

### mod 5 partition identity proof

I am looking for a proof that:
$$\prod_\limits{m=0}^\infty \dfrac{1}{(1-x^{5m+1})}=\sum_\limits{i=0}^\infty \dfrac{x^i}{\prod_\limits{j=1}^i (1-x^{5j})}$$
The left hand side expands into:
...

**8**

votes

**1**answer

91 views

### How many uniquely colored degree two vertices in 3-coloring of subcubic graph?

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as ...

**1**

vote

**2**answers

119 views

### question about literature in the field of Ramsey's theory [on hold]

i am searching for an on- line paper or a book, or maybe just a paper or a book which consists a proof of finite Ramsey's theorem for sets (not for graphs). i need a combinatorial proof which is not ...

**0**

votes

**1**answer

119 views

### Frankl's union-closed sets conjecture for infinite families

This question is motivated by Frankl's union-closet sets conjecture.
Let $X$ be a non-empty set. We say that a family ${\cal A} \subseteq {\cal P}(X)$ is union-closed if $\emptyset\notin{\cal A}$ and ...

**1**

vote

**1**answer

942 views

### A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...

**2**

votes

**1**answer

49 views

### Induced matching of cycle

Definition:
A graph $G$ is chordal if every induced cycle in $G$ has length 3, and is co-chordal if the complement graph $G^c$ is chordal.The co-chordal
cover number, denoted $cochord (G)$, is the ...

**0**

votes

**0**answers

98 views

### Ramanujan graphs and stable real polynomials

I have a problem with the lemma 6.5 and the theorems 5.1, 6.6 in the paper of Adam Marcus, Daniel Spielman and Nikhil Srivastava. http://arxiv.org/pdf/1304.4132.pdf
I do not understand how they use ...

**2**

votes

**1**answer

73 views

### Discrepancy of elements in minimal members of a union-closed set

This question is motivated by Frankl's union-closet sets conjecture.
Let $n\in\mathbb{N}$ and set $[n] = \{0,1,\ldots,n\}$. We say that a family ${\cal A} \subseteq {\cal P}([n])$ is union-closed if ...

**1**

vote

**3**answers

1k views

### Laplacian spectrum for product graphs

Let $G$ and $H$ be simple graphs.
I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong ...

**0**

votes

**1**answer

189 views

### Order-Perserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...

**11**

votes

**1**answer

240 views

### A sum over characters of the symmetric group

Let $C_\mu$ be the size of the conjugacy class in $S_n$ of permutations whose cycletype is the partition $\mu\vdash n$. Let $\chi$ be the characters of the irreducible representations of $S_n$.
Let ...

**7**

votes

**1**answer

867 views

### Coin problem with permutations

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers.
It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c ...

**22**

votes

**1**answer

693 views

### Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...

**9**

votes

**1**answer

298 views

### Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...

**19**

votes

**2**answers

640 views

### How many simplicial complexes on n vertices up to homotopy equivalence?

Fix a number $n$, and define $\gamma(n)$ to be the number of simplicial complexes on $n$ unlabeled vertices up to homotopy equivalence. It is unlikely that an explicit formula exists, but what is ...

**1**

vote

**1**answer

79 views

### Vectors which average to zero over any graph neighborhood

Given an undirected connected graph on $n$ nodes, let $S$ be the subspace of vectors $x \in \mathbb{R}^n$ which satisfy $$\sum_{j \in N(i)} x_j = 0,$$ for all $i=1, \ldots, n$. Here $N(i)$ is the set ...

**7**

votes

**1**answer

865 views

### Van Den Berg-Kesten-Reimer inequality

Van Den Berg-Kesten-Reimer inequality
For a given positive integer $n$ and for every $i\in[n]$, denote by $\mu_i$ a probability measure on a finite set $\Omega_i$. Call $\mu$ and $\Omega$ the ...

**5**

votes

**1**answer

163 views

### How often can subsets of a universe intersect exactly once?

My question is inspired by the following observation:
Claim: It is not possible to choose $n$ subsets of the universe $[n]$, each of size $\Omega(n)$, such that for each subset $S$ and each element ...

**7**

votes

**1**answer

120 views

### Classifying two-faces of four-polytopes

Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to ...

**11**

votes

**1**answer

845 views

### Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...

**4**

votes

**1**answer

134 views

### Point-Hyperplane incidence in finite projective spaces

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...

**4**

votes

**1**answer

132 views

### Probability bound for perfect matching

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**15**

votes

**11**answers

2k views

### Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...

**2**

votes

**2**answers

142 views

### Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides

How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?
I've done some work on this and have found a way of calculating this that's ...

**5**

votes

**1**answer

190 views

### Does this notion related to species/operads/FI-modules have a name?

Let $B$ be the symmetric monoidal category of finite sets and bijections with disjoint union. Let $C$ be a symmetric monoidal category. Is there a standard name for a lax monoidal functor $F:B \to C$? ...