Skip to main content
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 ...
Emil Jeřábek's user avatar
8 votes

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$ ...
Neal Young's user avatar
  • 10.8k
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$...
David Eppstein's user avatar
7 votes

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).
tomil's user avatar
  • 71
5 votes

Concrete version of KKL Theorem

See Exercise 9.30 of Ryan O'Donnell's Analysis of Boolean Functions book [1]: for any $f\colon\{-1,1\}^n\to \{-1,1\}$, $$ \mathbf{MaxInf}[f]\geq \frac{1}{2}\mathbf{Var}[f]\cdot \frac{\ln n}{n} (1-o(1))...
Clement C.'s user avatar
  • 4,471
5 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 &...
Chris Jones's 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 \...
William Hoza's user avatar
  • 1,743
4 votes

Algorithm to check whether a given set is Sidon

In what range are the values in your set $S$? Note that if the range is not too large you can represent $S$ by a polynomial $P_S$ ($P_S = \sum_{s \in S} x^s$) and compute $P_S^{2}$ with the FFT ...
Bernardo Subercaseaux's user avatar
3 votes
Accepted

Cover a graph with complete graphs

Here are asymptotic bounds for $k(n, m)$ that are tight up to a logarithmic factor. Note the threshold around $m = \Theta(n^{3/2})$: Theorem 1. $~~~~\frac{1}{21}\min(\lceil\sqrt n\rceil, \lceil m/(n\...
Neal Young's user avatar
  • 10.8k
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 ...
user3508551's user avatar
  • 1,153
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\}...
Clement C.'s user avatar
  • 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 ...
GMB's user avatar
  • 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 ...
Laakeri's user avatar
  • 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 ...
Andrew Morgan's 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=[...
Aryeh's user avatar
  • 10.6k
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 ...
D.W.'s user avatar
  • 12.2k

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