9 votes
Accepted

Computational complexity of Turán-type problems

Since $r$ has to be an integer, I assume $n$ is even. I’m pretty sure the discussion below works for $n$ odd as well, if you decide whether you want $r=(n+1)/2$ or $r=(n-1)/2$ and adjust the bound ...
user avatar
8 votes

Constant in Komlos conjecture

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-...
user avatar
7 votes
Accepted

On the coloring number of small graphs with small cliques

Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$. As for $k^2$...
user avatar
5 votes
Accepted

Upper bound for number of independent sets

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.
user avatar
4 votes
Accepted

"Parity testing set" for disjoint pairs of sets

Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased if for every nonempty set $P \subseteq [n]$, we have $$ \left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \...
user avatar
  • 1,733
4 votes

Constant in Komlos conjecture

Taking the $v_i$ to be the columns of this matrix shows $c \geq \frac{4}{\sqrt{6}} \approx 1.633$ (I found and verified the matrix by computer experiment): $$M = \frac{1}{\sqrt{6}}\begin{pmatrix} 1 &...
user avatar
3 votes

Upper bound for number of independent sets

If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges. $I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any ...
user avatar
2 votes

Which (almost) balanced Boolean function has smallest "total" influence

You have the lower bound of $\mathbf{Inf}[f] \geq \operatorname{Var}[ f ]$ for $f\colon \{-1,1\}^n\to\mathbb{R}$ (Poincaré Inequality), so that for an (almost) balanced $f\colon \{-1,1\}^n\to\{-1,1\}...
user avatar
  • 4,341
2 votes

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

Using Chandra's hint, I think I got the idea. We bounded the probability: $$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$ Now consider an item of size $s_i$ that was left. It was ...
user avatar
1 vote

Regularity Lemma for Multi-Relational Graphs?

(Expanding on my comment) First off: there are two different common phrasings of the SRL in the literature. Both ought to generalize to your $m$-color setting, but in a slightly different way, so let ...
user avatar
  • 2,313
1 vote

On structure of graphs with average degree equal to maximum average degree

This question is a bit open-ended, but here are some observations: Some non-regular graphs can have this property, for example all trees have this property. For graph coloring, this property seems to ...
user avatar
  • 1,432
1 vote
Accepted

A Combinatorial Problem on Extremal Set Theory

This is arguably trivial, but maybe good enough for you: For any $a,b,c$ with $b \le a \le c$ (in particular $a=b=c$), if $\mathcal{F}$ is maximal subject to (i) and (ii), then it satisfies (iii) for ...
user avatar
1 vote

A Combinatorial Problem on Extremal Set Theory

Did you want some condition to make $\mathcal{F}$ a large collection? Because the current definition allows for the following, presumably trivial, case. Consider $\mathcal{F}=\{S_1,S_2\}$, where $S_1=[...
user avatar
  • 10.1k
1 vote

reference request- property of subset of rows in a matrix

Your problem can be solved in polynomial time, by reduction to bipartite matching. In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired ...
user avatar
  • 10.5k

Only top scored, non community-wiki answers of a minimum length are eligible