# Tag Info

9

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 according to the statement of Turán’s theorem. I find it easier to express the problem in terms of the complement of your graph. Then it becomes: given a graph $G$ ...

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

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 & -... 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 \... 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