# Tag Info

8

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\}$-linear combinations are as long as possible (note that this is just an interesting special case, I'm not saying that it is opotimal in any way). This is achieved ...

7

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$-vertex triangle-free graphs, their chromatic number can be $\Theta(k/\sqrt{\log k})$ (and not higher); see Kim, Jeong Han (1995), "The Ramsey number $R(3,t)$ ...

6

I think the answer is $\Theta(\log n)$ and the proof is the same as the classic Ramsey-theorem proof. On one hand, you always have a complete or empty subgraph with these many vertices. On the other, a random graph won't have a large induced $C_4$-free subgraph. For this latter, bound the number of induced subgraphs on $t$ vertices by $n^t$ and for each ...

6

We can do $2\sqrt{n}-1$; consider the complete $\sqrt{n}$-partite graph, as long as there are two parties both with more than one node inside there is an induced $C_4$, so it cannot be inteval. Therefore we have to remove at least $(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$ nodes to destroy all the induced $C_4$.

6

Here is a sketch on how to do almost what you want, but not quite. It only proves a $k^{k+\operatorname{polylog}(k)}\log n$ bound. Consider a set of size $m=n\log_2 k$ which we think of as $n$ groups on $\log_2 k$ elements each. Next construct an $(m,k\log_2 k)$-universal set family $F$ of size $2^{k\log k+\operatorname{polylog}(k)}\log m$ using the ...

5

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.

4

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 \frac{\epsilon}{2}.$$ In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\... 4 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 & 1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & 1 & -1 & -1\\ -1 & 1 & 1 & 1 & 1 & 1\\ -1 & 1 & 1 & -... 3 I am not sure if these results are known. If you define the t-thick upper (or lower, does not matter) shadow of A_k as the sets of one level higher (resp. lower) that contain (resp. are contained in) at least t sets from A_k, then what you ask for is the (k+1)/2-thick upper shadow. As far as I know it is open to determine the size of the smallest ... 3 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 graph with a matching of size 3 has at most 3^3\times 2^{n-6} independent sets, then show that we can not have two node disjoint paths of length 3 and no ... 2 I update my reply in light of Aravind's comment. The claim in my previous answer was clearly incorrect but, in my defence, I never had a good intuition about graphs. By adapting Aravind's argument you can show an upper bound of O(\sqrt{n}), as every n-vertex perfect graph has an independent set or a clique of size \sqrt{n}. It should be possible to ... 2 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\} one must have$$ \mathbf{Inf}[f] \gtrsim 1 \tag{1}$$(say,$1-\epsilon$, depending on the near-unbalanced assumption). Further, for a dictator function, ... 1 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 free. So if you're okay with the$b \le a \le c$condition, then you can otherwise pick the parameters however you want, and then greedily build$\mathcal{F}$. ... 1 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=[n/2]$and$S_2=[n]\setminus S_1$. Then we can take$a=n/2$,$b=n$,$c=n/2$. 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 property. Construct an undirected bipartite graph with$m$left-vertices (one per row) and$n$right-vertices (one per columN). Add an edge$(i,j)$whenever$M_{i,j}...

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