Lower bound on transversal number of a specific hypergraph

136 Views Asked by At

Let $d\geq 2$ be an integer. I will define a hypergraph $H=(V,E)$ as follows. The vertex set is the set of all binary words of length $d$, i.e., $V=\{0,1\}^d$. The edges are sets of vertices that have the same two fixed coordinates, i.e., $E=\{e_{ij}^{ab}:1\leq i<j\leq d\wedge a,b\in\{0,1\}\}$ such that $$e_{ij}^{ab}=\{(x_1,\ldots,x_d)\in V:x_i=a\wedge x_j=b\}.$$

Note that $|V|=2^d$, $|E|=4\binom{d}{2}$ and the hypergraph is $\binom{d}{2}$-uniform.

I wonder about a lower bound on the transversal number (minimum vertex cover) of this hypergraph. For $d=2$, the edges are disjoint so I need $4$ vertices to cover each edge. For $d=3$, I can cover all edges with also $4$ vertices $\{000,110,101,011\}$. I believe for $d=4$ we cannot cover all edges with just $4$ vertices. Is there a reasonable lower bound on this?

Note that the size of maximum set of independent edges is $4$, so this trivial bound is not useful. And I don't know any other technique to give a lower bound on transversal number.

1

There are 1 best solutions below

0
On BEST ANSWER

I can prove that the transversal number is between $\lceil \log_2 d \rceil$ and $2 \lceil \log_2 d \rceil + 2$.


First of all, a construction: in $d = 2^k$ dimensions, we can cover all these edges with $2k+2$ vertices. I'll start with an example for $k=3$: we take the vertices \begin{array}{ccc} 00001111 & \quad & 11110000 \\ 00110011 & \quad & 11001100 \\ 01010101 & \quad & 10101010 \\ 00000000 & \quad & 11111111 \end{array} In general, we can represent a coordinate $i$, $1 \le i \le d$, by an element of $\{0,1\}^k$; we'll write $B_1(i), B_2(i), \dots, B_k(i)$ for the coordinates of this representation. Then the $2k+2$ vertices we choose are as follows: for each $t$, $1 \le t \le k$, we take the two vertices $$(B_t(1), B_t(2), \dots, B_t(d)) \text{ and } (1-B_t(1), 1-B_t(2), \dots, 1 - B_t(d)).$$ We also take the two vertices $000\dots0$ and $111\dots1$.

For any two coordinates $i$ and $j$, there is some $t$ such that $B_t(i) \ne B_t(j)$, and therefore the two vertices we chose for that $t$ cover $e_{ij}^{10}$ and $e_{ij}^{01}$. Also, the last two vertices cover $e_{ij}^{00}$ and $e_{ij}^{11}$ for any $i$ and $j$.


Next, the lower bound. If there are $n$ vertices $v_1, \dots, v_n$ chosen, consider the vector $((v_1)_i, (v_2)_i, \dots, (v_n)_i)$ for each coordinate $i$. If $d > 2^n$, then by the pigeonhole principle there are two coordinates $i$ and $j$ such that $$((v_1)_i, (v_2)_i, \dots, (v_n)_i) = ((v_1)_j, (v_2)_j, \dots, (v_n)_j)$$ and therefore no vertex chosen covers the edge $e_{ij}^{10}$ or $e_{ij}^{01}$.

So in any vertex cover, we must have $2^n \ge d$, or $n \ge \log_2 d$ (which implies $n \ge \lceil \log_2 d \rceil$).