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
1answer
95 views

Spectra of undirected $d$-regular graphs

Let $G$ be a undirected $d$-regular graph, that is, a graph whose all vertices have the same degree $d$. It is known that the eigenvalues $\sigma_i$, $i=1,\cdots,n$, of the adjacency matrix are real ...
5
votes
1answer
235 views

Zero-sum sets in union-closed families

The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ ...
1
vote
1answer
139 views

Probability of covering a set

Suppose we have a set of $N$ numbers. At any given trial we can randomly choose $N^{1-a}$ of the numbers where $a\in(0,1)$. We replace the numbers back. How many trials does it take in average case ...
1
vote
0answers
37 views

Is the complement of a vertex figure in an (abstract) polytope connected?

I consider an (abstract) regular polytope $P$, and $H$ a vertex figure of $P$. Is the complement $P \setminus H$ connected (as a poset, in the sense that its Hasse diagram, ignoring the improper ...
4
votes
2answers
250 views

What is the independence number of this graph which is a generalization of a Kneser graph?

Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two ...
0
votes
0answers
91 views

Multidimensional recurrence relations

There are many methods of solving one-dimensional homogeneous linear recurrence relations, i.e. such of the form $$ a_n = \sum_{k=1}^{m}\alpha_ka_{n-k}.$$ Most widespread use linear algebra or ...
12
votes
4answers
515 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 ...
2
votes
1answer
139 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 ...
7
votes
0answers
134 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
119 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
84 views

A combinatorial sum involving ratios of binomials [closed]

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

Mapping a grayscale image into a weighted undirected graph

I am looking for a method to convert an image into a network. I have found the study Z. Wu, X. Lu, Y. Deng, Image edge detection based on local dimension: A complex networks approach. Physica A ...
4
votes
0answers
182 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 ...
13
votes
3answers
1k 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) ...
1
vote
0answers
57 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
354 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
178 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
147 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
243 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
163 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
74 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$, ...
2
votes
0answers
91 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
2answers
550 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
118 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 ...
11
votes
2answers
655 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
149 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
133 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
69 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
80 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
votes
1answer
220 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
111 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
83 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 ...
1
vote
0answers
19 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
283 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
158 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
255 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
168 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
273 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 ...
1
vote
0answers
51 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
142 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
228 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
163 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
76 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
351 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
391 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 ...
2
votes
0answers
89 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,\ldots,H_{r-1},H_r=H' \} \subseteq P$ so ...
2
votes
1answer
228 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 ...
5
votes
0answers
93 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
119 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$ ...
1
vote
2answers
206 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$ ...