All Questions
Tagged with lower-bounds co.combinatorics
16 questions
17
votes
6
answers
10k
views
Lower bounds for chromatic number of a graph
I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
- 1,791
6
votes
1
answer
1k
views
Simple lower bounds for Bell numbers (number of set partitions)?
The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements.
It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, ...
- 2,350
5
votes
4
answers
917
views
Limit of a sum with binomial coefficients
Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$
$$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$
$$C_k = \frac{\sum_{i=1}^k(...
- 155
5
votes
3
answers
4k
views
Proofs of Lower Bounds for Ramsey Numbers?
As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...
- 23k
5
votes
1
answer
1k
views
Best lower bound for off-diagonal Ramsey numbers
What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? (...
3
votes
1
answer
167
views
Lower bound on the sum of pmf squared of a hypergeometric distribution
I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant ...
- 33
3
votes
0
answers
683
views
Counting / characterizing the isolated points of a particular algebraic variety
I'm not a professional geometer / topologist, so please thanks for your patience :)
Setup
The following questions are the first in a series of steps I'm undertaking in an attempt to break down a ...
- 6,853
3
votes
0
answers
212
views
Lower bound on number of $r$-regular graphs witn $n$ vertices
Consider the set of $r$-regular labeled graphs with $n$ vertices. There are results on its asymptotic size (see for instance this question on MO).
Is there a known, explicit lower bound on that size, ...
- 81
3
votes
0
answers
268
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 ...
user76479
2
votes
1
answer
383
views
Lower bound and limit of a sum with binomial coefficients
Let
$$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$
$$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$
$$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
- 155
2
votes
1
answer
205
views
When does the equality hold in Dias da Silva - Hamidoune Theorem?
Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
- 167
2
votes
1
answer
96
views
Lower bound on the number of balanced graphs
Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...
- 143
2
votes
1
answer
140
views
Minimum local permutation data needed to globally merge locally sorted sequences?
We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.
Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...
- 1,826
1
vote
0
answers
113
views
Bounds on spectral radius using chromatic number
I am struggling with this question:
If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...
- 135
0
votes
0
answers
134
views
Spread of a disease on a modular chessboard (torus) - lower bound
I learned about the following result from one of Peter Winkler's books:
It is impossible to infect the entire $n\times n$ chessboard (usual chessboard) starting from fewer than $n$ infected cells.
The ...
- 1
0
votes
0
answers
131
views
Estimating when does a certain binomial sum exceed an upper bound
Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = 1,f_{...
- 3,463