# Tag Info

## Hot answers tagged extremal-combinatorics

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

### Algorithm to check whether a given set is Sidon

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, per [1]: Corollary 1.2 [1]. Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ ...
• 10.8k
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$...
• 51.1k

### What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

The smallest such example that is known to the House of Graphs is for $k = 9$. There is a graph of tree-width $9$ having only $44$ edges (while the $10$-clique contains $45$ edges).
• 71

• 243
Accepted

• 1,153
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,471 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,403 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,786 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,429 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 ...