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
45 views

The line graph of a complete graph [on hold]

Show that there exist a $\left\{P_{5},C_{4}\right\}$- decomposition of the graph $L(K_{9})$.
0
votes
0answers
139 views

Has the attempt of proof of the Frankl conjecture by Vladimir Blinovsky been checked? [on hold]

I found his article in arxiv: http://arxiv.org/pdf/1507.01270.pdf. But i didn't find any response to the article and as I'm an undergraduate I have no knowledge to judge if this approach is promising. ...
11
votes
4answers
361 views

List of counting proofs instead of linear algebra method in combinatorics

I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its ...
1
vote
0answers
62 views

Counting growing tree trajectories

I am looking for help: Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is ...
5
votes
0answers
97 views

Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?

The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1. Has anyone seen these trees? The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
0
votes
0answers
108 views

Additional condition to the Bollobas theorem (Sperner's therorem) 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 ...
2
votes
0answers
69 views

A combinatorial sum involving ratios of binomials [on hold]

Can anyone suggest how to prove the following (for $k \le n$): $$\sum \limits_{s=0}^N \frac{\binom{n}{k} \binom{N-n}{s-k} }{\binom{N}{s}} = \frac{N+1}{n+1}$$ I am assuming it to be true, and ...
1
vote
0answers
116 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 ...
11
votes
1answer
346 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) ...
-6
votes
0answers
35 views

Arrange numbers? [closed]

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 ...
1
vote
0answers
54 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 ...
7
votes
1answer
318 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 ...
2
votes
1answer
139 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 ...
7
votes
1answer
126 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 ...
6
votes
3answers
218 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 ...
3
votes
0answers
144 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 ...
0
votes
1answer
66 views

writing an integer as particular summation [closed]

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
84 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 ...
-5
votes
0answers
53 views

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

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
524 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
94 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 ...
10
votes
2answers
602 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), ...
0
votes
1answer
122 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
2answers
120 views

question about literature in the field of Ramsey's theory [closed]

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 ...
2
votes
1answer
51 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 ...
2
votes
1answer
74 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 ...
0
votes
1answer
193 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 ...
0
votes
0answers
100 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 ...
1
vote
1answer
80 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 ...
0
votes
0answers
13 views

The complexity of Max-K interval selection

I came up with the following problem, but do not know how to analyze it. Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in ...
7
votes
2answers
261 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} ...
2
votes
2answers
144 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
198 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$? ...
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 ...
11
votes
1answer
242 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 ...
0
votes
0answers
12 views

Approximation preserving reductions [on hold]

I've seen in the following document https://hal.archives-ouvertes.fr/hal-00958028/document A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...
1
vote
0answers
45 views

Directed graph Laplacian with exactly one negative eigenvalue

Let $G$ be a digraph with adjacency matrix $A =(A_{ij})$ where $A_{ij}=1$ if and only if there is a directed edge $i \to j$ and $A_{ij}=0$ otherwise. Let $D= (D_{ij})$ be the degree matrix with ...
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 ...
3
votes
4answers
216 views

How small can a set system containing a large subset of every set be?

Fix $1>c>0$. Consider the set $[n]=\{1,2,\ldots,n\}$ and the set of all subsets of this set which we'll denote as $2^{[n]}$. Let $S \subseteq 2^{[n]}$ be a set system such that for every ...
2
votes
1answer
150 views

Extracting a full rank matrix from a 0-1 matrix

If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...
3
votes
1answer
70 views

Generalizations of the Triangle Removal Lemma to smaller exponents

The Triangle Removal Lemma states: For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by ...
10
votes
2answers
277 views

Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line? Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = ...
2
votes
2answers
368 views

Closed formula for the generating function of the sequence of powers

Does anyone know of a closed formula for the function $f_k(x)=\sum_{n=1}^{\infty}{n^k x^n}$ ? That is, the generating function of the sequence $1^k,2^k,3^k...$. It is not hard to see that ...
0
votes
0answers
133 views

Shortest distance on a combinatorial chess board

Consider a random $n\times n$ combinatorial $0/1$ square matrix over field $\Bbb F$ of rank $r$ with every row distinct and every column distinct as a chess board. Definition of combinatorial ...
0
votes
0answers
41 views

Inapproximability of Combinatorial Optimization Problems

I've been reading the "Inapproximability of Combinatorial Optimization Problems" by Luca Trevisan (see: link). On pages 3-4 it mentions that a polynomial time algorithm for 3SAT would exist if there ...
0
votes
0answers
52 views

Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,...,H_{r-1},H_r=H' \} \subseteq P$ so that ...
2
votes
1answer
219 views

Generalization of 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 ...
4
votes
0answers
85 views

For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?

There exists a Latin square of order $8$ which can be partitioned into $2 \times 4$ subrectangles: $$ \begin{bmatrix} \color{red} 1 & \color{red} 2 & \color{red} 3 & \color{red} 4 & ...
4
votes
0answers
112 views

Reference for the notion of polyhedra “degenerations”

Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that: a) $P(0)=P$; b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ ...
2
votes
2answers
178 views

Batched Coupon Collector Problem

The batched coupon collector problem is a generalization of the coupon collector problem. In this problem, there is a total of $n$ different coupons. The coupon collector gets a random batch of $b$ ...