Questions tagged [hypergraph]
Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
291 questions
5
votes
1
answer
188
views
Singletons, but not all subspaces complemented in $\text{Sub}(H)$
If $H=(V,E)$ is a hypergraph, we say that $T\subseteq V$ is a subspace with of $H$ if whenever $a,b\in T$ with $a\neq b$, then $e\subseteq T$ for every $e\in E$ having $\{a,b\}\subseteq e$. By $\...
- 56.5k
2
votes
2
answers
159
views
Maximal disjoint but not a complement in $\text{Sub}(H)$ for linear hypergraph $H$
If $H=(V,E)$ is a hypergraph, we say that $T\subseteq V$ is a subspace with of $H$ if whenever $a,b\in T$ with $a\neq b$, then $e\subseteq T$ for every $e\in E$ having $\{a,b\}\subseteq e$. By $\...
- 56.5k
6
votes
1
answer
329
views
Complements in the lattice of subspaces of a hypergraph $H= (V,E)$
Let $H = (V, E)$ be any hypergraph, that is $V$ is a set, and $E\subseteq{\mathcal P}(V)$.
We say that $T \subseteq V$ is a subspace of H, or alternatively, closed under the edges of H, if whenever $a,...
- 56.5k
2
votes
1
answer
124
views
The lattice of subspaces $\text{Sub}(H)$ of a hypergraph $H= (V,E)$
Let $H = (V, E)$ be any hypergraph, that is $V$ is a set, and $E\subseteq{\mathcal P}(V)$.
We say that $T \subseteq V$ is a subspace of H, or alternatively, closed under the edges of H, if whenever $a,...
- 56.5k
3
votes
1
answer
122
views
Cardinality of fibers in a $T_2$-hypergraph with large edges
We say that a hypergraph $H=(V,E)$ is $T_2$ if for all $v, w\in V$ with $v\neq w$, there are disjoint sets $e_1, e_2\in E$ with $v\in e_1, w\in e_2$.
For $v\in V$, let $e_v= \{e\in E: v\in e\}$.
Given ...
- 56.5k
3
votes
1
answer
269
views
Chromatic number of the maximal chain hypergraph on ${\cal P}(\omega)$
If $H=(V, E)$ is a hypergraph, the its chromatic number $\chi(H)$ is the smallest non-empty cardinal $\kappa$ such that there is a map $c:V \to \kappa$ such that for every $e\in E$ containing more ...
- 56.5k
2
votes
0
answers
113
views
Generating totally balanced hypergraphs on $n$ vertices
Let $H=(V,E)$ be an hypergraph, where $V$ is the vertices set and $E$ is the hyperedge set. A special cycle of $H$ is a sequence
$
(v_1, e_1, v_2, e_2, \ldots, v_{k}, e_{k})
$,
with $k \geq 3$, where $...
- 1,444
0
votes
1
answer
96
views
Finding large matchings in vertex transitive uniform hypergraphs
Let $\mathcal{H}$ consist of all subsets of finite group $\mathbb{Z}_n$ of cardinality $k$ (much smaller than $n$) such that their sums are $0$ (modulo $n$). Since picking any $k-1$ elements in the ...
- 2,330
2
votes
1
answer
176
views
Are $T_2$-hypergraphs with isomorphic intersection graphs isomorphic?
A hypergraph $H=(V,E)$ is said to be $T_2$ if for all $v_1\neq v_2\in V$ there are $e_1,e_2\in E$ with $v_1\in e_1, v_2\in e_2$ and $e_1\cap e_2=\emptyset$. The intersection graph $I(H)$ is defined by ...
- 56.5k
8
votes
1
answer
550
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 573
4
votes
1
answer
221
views
Minimal dominating sets in thin hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.
A subset $D\subseteq V$ is dominating if
$\bigcup \{e\in E:e\cap D \neq \...
- 56.5k
2
votes
1
answer
275
views
Connected partitions of bounded degree graphs with parts of bounded sizes
A connected partition of a graph is a partition of its vertex-set such that the induced subgraph on each part is connected.
Question 1: Are there real numbers $c\ge1$ and $r\ge1$ such that for any ...
- 573
2
votes
1
answer
234
views
Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$
Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be ...
- 56.5k
5
votes
1
answer
468
views
4-color theorem for hypergraphs
Question. Does every hypergraph that does not admit a complete minor with $5$ elements have a coloring with $4$ colors?
Below are the definitions to make this precise.
If $H = (V, E)$ is a hypergraph ...
- 56.5k
1
vote
1
answer
137
views
Isomorphic hypergraph duals
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
We say hypergraphs $H_i=(V_i, E_i)$ for ...
- 56.5k