Search Results

Let $A$ and $B$ be disjoint sets of size $n$, and let $H$ be the hypergraph with vertex set $A \cup B$, whose hyperedges are all $3$-subsets $e$ of $A \cup B$ such that $|e \cap A| \in \{1, 2\}$. …

I think they exist for all $k \geq 2$. Here is a proof. Fix an enumeration of $[\omega]^2$. For the first step in the process add an arbitrary $k$-set $q_1=q(p_1)$ containing the first pair $p_1$ of …

Then add a hyperedge $e$ of size $n-1$ containing $x$ to make the hypergraph connected. … Let $\mathcal{H}$ be a hypergraph on $[n]$ with more than $3 \cdot 2^{n-2}$ hyperedges. …

For all even $n \geq 16$, $N:=\binom{n/2}{2}$ is the right answer. Semi-proof. Let $n=2k$ and observe that $4N=2k(k-1)$. Thus, if more than $N$ sets appear, then some element $x$ occurs in at leas …

Indeed we can define a cycle in a hypergraph as a sequence of distinct alternating vertices and hyperedges $C:=v_1, E_1, v_2, E_2, \dots, v_n, E_n, v_1, E_1$, where $v_i \in E_i \cap E_{i+1}$ for all $ … Let $\mathcal{H}$ be a hypergraph where each hyperedge contains at least 3 vertices. …

Yes, there is always such a map. Let $k$ be the number of vertices in each edge of $H=(V,E)$. Consider an arbitrary vertex $v \in V$ and choose $e \in E$ such that $v \notin e$. For each $w \in e$ …

No, not every sane hypergraph is summable. To see this, let $G$ be a star with five leaves $\ell_1, \dots, \ell_5$ all adjacent to a vertex $u$. … Then turn $G$ into a sane hypergraph $H$ by adding the hyperedges $\{\ell_1,\ell_2\}$ and $\{\ell_3, \ell_4, \ell_5\}$. …

Given a hypergraph $H=(V,E)$ and $X \subseteq V$, we say that $X$ is shattered if for all $X' \subseteq X$, there exists $e \in E$ such that $e \cap X=X'$. … Given a finite dimensional vector space $\mathbb V$, let $H$ be the hypergraph with vertex set $\mathbb V$ and whose edges are the subspaces of $\mathbb V$. …

Let $H=(V,E)$ be a finite hypergraph such that $|e| > 1$ for all $e \in E$ and for all distinct $e_1, e_2 \in E$, $|e_1 \cap e_2| \neq 1$. Then $H$ is $2$-chromatic. Proof. …

This problem seems pretty hard. Let $G$ be a bipartite graph with bipartition $(A,B)$. One easy case to consider is if each vertex in $A$ has degree $k$ and we seek a maximum $(1, k)$ matching. For …

To expand on Steve D's comment, the answer is indeed yes for finite abelian groups. The following is a simplified version of an earlier proof (rendering some of the below comments obsolete). Proof. …

Yes, this is possible. For each prime $p$ and $c \in \{0,1, \dots, p-1\}$ let $A_{c,p}=\{c+kp \mid k \in \mathbb{Z}\}$. Clearly, the set of all $A_{c,p}$ is a clutter $\mathcal C$ with ground set $\ …

Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. …

This is a special case of Ryser's Conjecture, which states that in an $r$-partite, $r$-uniform hypergraph (with $r>1$) $\tau \leq (r-1) \nu$, where $\tau$ is the size of a minimum cover and $\nu …