# Tag Info

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 ...
• 14.8k

### 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\}$-...
• 2,470
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$...
• 50.3k
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.
Accepted

• 233

### 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 ...
• 1,319
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\}... • 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 ... • 680 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 ... • 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 ... • 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 ... • 1,419 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=[...
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 ...