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)$ ...


4

Håstad, Jukna, and Pudlák used the sunflower lemma to prove lower bounds on depth-$3$ $AC^0$ circuits: http://www.csc.kth.se/~johanh/topdowndepth3.pdf This is also explained in Section 6.3 of the book of Jukna on extremal combinatorics, and in Section 11.3 of his book on boolean function complexity.


4

Razborov's lower bound on the size of monotone boolean circuits for the clique problem is an early application in TCS.  A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357. A good reference for learning about this is chapter 9 in Jukna's book "Boolean Function Complexity: Advances and ...


4

Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see: Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.


4

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/


3

You can notice that $SN_i$ is maximum if $P_i$ is a clique of size $|P_i|$. So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P_i$ have the same size. But the problem of partitioning a graph into 3 cliques of the same size is still NP-...


3

This is #P hard via counting solution to monotone DNF formula. Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables. We are trying to find regular language $L$ over alphabet $\{0,1\}$ with all words of length $n$ and the words in $L$ are in one to one correspondence with the satisfying assignment of $\phi$. Variable $x_i$ in $\phi$ corresponds to $...


2

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1. Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum ...


2

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$. Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it ...


2

The statement of the problem is incorrect. But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is: Assume $G$ is connected. Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the ...


1

I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there exists graphs of degree at most $\Delta$ and girth at least $g$ with independence ratio at most $2\log \Delta/\Delta$. In contrast, as you mention, the Frieze ...


1

Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2. Instead, you can ask the question of what is the maximum column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is $O(\sqrt{k})$. This is known as ...


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