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
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
2answers
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
3answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
6answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
11answers
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
2answers
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
1answer
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$? ...