# Questions tagged [hypergraph]

Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.

**0**

votes

**0**answers

15 views

### Hypergraph mapping's projection

I have been struggling quite a while with a question, which I suspect might have a simple answer to:
I have a Graph G = (X,E,Ψ) with E (hyperedge) being a family of subsets of X and Ψ being a mapping ...

**0**

votes

**1**answer

71 views

### Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**1**

vote

**0**answers

29 views

### Is there an algorithm for this constrained Hypergraph optimization problem?

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...

**3**

votes

**1**answer

104 views

### A set coverage problem

Given a set $X$ and $k\in\mathbb{N}$ we call a subset of $X$ a $k$-subset if its cardinality is $k$. If ${\cal S}$ is a collection of subsets of $X$ and $x\in X$ we set ${\cal S}_x=\{S\in {\cal S}: x\...

**4**

votes

**1**answer

60 views

### Optimal pseudotransversals

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**0**

votes

**1**answer

60 views

### Expected sum of chosen coordinates in a random subset of a Hamming hypercube

Let $S$ = $\{v_1, v_2, ..., v_n\}$ denote a random subset of a Hamming hypercube of dimension $d$, where $n = |S|$ and $n \leq 2^d$. If $v_i$ = $\langle x^i_1x^i_2... x^i_d\rangle$ for all $i \in [1,n]...

**3**

votes

**1**answer

65 views

### $|V|$ and $|E|$ in hypergraphs with a separation property

Let $H=(V,E)$ be a hypergraph. We call it $T_0$ if for all $x\neq y \in V$ there is $e\in E$ with $\{x,y\}\not\subseteq E$ and $\{x,y\}\cap e\neq \emptyset$ (i.e., $e$ contains exactly one of $x,y$).
...

**19**

votes

**3**answers

806 views

### Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...

**2**

votes

**1**answer

48 views

### $3$-uniform hypergraph with $n$ vertices and $O(n^{3/2})$ hyperedges

Suppose $H=(V,E)$ is a $3$-uniform hypergraph with $n$ vertices $V$ and $O(n^{3/2})$ hyperedges, $E.$
My question is: How many vertices do I need to delete to make sure all hyperedges are destroyed? ...

**2**

votes

**1**answer

244 views

### How does the high-dimensional combinatorial Laplacian work?

When considering the boundary and coboundary maps, we have the common definitions that the boundary map based on the space of chains $C_k(X)$ is $$\partial_k([v_0,...,v_k])=\sum_{i=0}^k (-1)^i[v_0,...,...

**5**

votes

**0**answers

122 views

### Hopf algebra interpretation of hypergraph duality?

The work of Aguiar and Ardila (https://arxiv.org/abs/1709.07504) on Hopf monoids for generalized permutohedra gives a Hopf monoid structure on the collection of hypergraphs; see sections 19 and 20 of ...

**0**

votes

**1**answer

55 views

### Standard names of two finitary properties of hypergraphs?

Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...

**4**

votes

**1**answer

176 views

### Minimal covers in hypergraphs with finite edges

Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq E$ is a cover if $\bigcup C = V$. Let $H$ be a hypergraph with the following properties:
$\bigcup E = V$,
all members of $E$ are finite, and
$d,...

**2**

votes

**1**answer

73 views

### Example of self-dual hypergraph with infinite edges

What is an example of a hypergraph $H=(V,E)$ with $|e|\geq \aleph_0$ for all $e\in E$ and the property that $H\cong H^*$ where $H^*$ is the dual hypergraph of $H$?

**5**

votes

**1**answer

176 views

### A set-family game

Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each ...

**3**

votes

**0**answers

51 views

### Clique number for hypergraphs

Does anybody know any link/source where I can find examples of hypergraphs with their clique numbers? I need a few examples to test an algorithm and do not want to go for randomly generated hypergraph....

**1**

vote

**2**answers

149 views

### Maximum intersecting set families of $\{1,\ldots,n\}$

Let $n\geq 3$ be an integer. We call a family ${\cal C}$ of subsets of $\{1,\ldots,n\}$ intersecting if it has the following properties:
$A, B\in {\cal C}$ implies $A\cap B \neq \emptyset$, and
$A \...

**8**

votes

**1**answer

205 views

### A generalization of Erdős-Ko-Rado theorem

Is there any result known about the following generalization of the Erdős-Ko-Rado theorem?
Let $n, k, r, s$ be positive integers. We call a family $\mathcal{F}$ of $k$-element subsets of $\{1,\ldots, ...

**1**

vote

**1**answer

57 views

### Strong and weak chromatic number of infinite bounded hypergraphs

This is a follow-up of an older question.
Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak ...

**1**

vote

**0**answers

83 views

### Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?

Definition. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in ...

**1**

vote

**1**answer

60 views

### Strong and weak chromatic number of infinite hypergraphs of finite rank

Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the ...

**0**

votes

**1**answer

84 views

### Why not have many edges instead of one edge connecting to many nodes (in hypergraphs) [closed]

As a follow-up to What are the Applications of Hypergraphs, the linked article:
Learning with Hypergraphs: Clustering, Classification, and Embedding
Mentions this:
Let us consider a problem of ...

**4**

votes

**0**answers

99 views

### Set version of ramsey type problem

For two sets of numbers $A,B$, write $A<B$ iff $\max A<\min B$.
For a sequence of integers $a_0,\cdots,a_{n-1}>0$,
let $Prop(a_0,\cdots,a_{n-1})$ denote the following proposition:
Given $n$ ...

**6**

votes

**1**answer

307 views

### Ramsey type theorem

Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$.
Is the following true?
For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...

**4**

votes

**1**answer

160 views

### Complexity for calculating number of Perfect Matchings in k-regular hypergraph

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices).
...

**7**

votes

**2**answers

315 views

### Infinite projective plane with small edges

Let $\kappa$ be an infinite cardinal. We say $E\subseteq {\cal P}(\kappa)$ is an infinite projective plane on $\kappa$ if
$e_1\neq e_2\in E$ implies $|e_1\cap e_2| = 1$, and
whenever $n\neq m\in \...

**-2**

votes

**1**answer

80 views

### Partitioning finite hypergraphs with edges [closed]

Let $H=(V,E)$ be a hypergraph such that $|V|$ is infinite, and the following statements hold:
if $a\neq b\in E$ then $|a\cap b|\leq 1$, and
every vertex $v\in V$ is contained in at least $2$ members ...

**0**

votes

**1**answer

127 views

### A weak version of the Erdös-Faber-Lovasz conjecture

A hypergraph is a pair $H=(V,E)$ where $V$ is a nonempty set, and $E\subseteq {\cal P}(V)\setminus\{\emptyset\}$ is a collection of non-empty subsets of $V$.
Strong colorings. If $\kappa$ is a ...

**2**

votes

**0**answers

45 views

### An equation involving fractional covering number of hypergraphs

Let $\mathcal{H}=(S,\mathcal{X})$ be a hypergraph, where $S = \{ s_1, \ldots, s_n \}$, and $\mathcal{X} = \{ X_1, \ldots, X_m \}$.
The dual hypergraph $\mathcal{H}^*$ of $\mathcal{H}$ is the ...

**1**

vote

**1**answer

133 views

### Choice sets in “thick” sets of sets

Let $X\neq \emptyset$ be a set and let ${\cal S} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ be a collection of non-empty subsets of $X$. We say $C\subseteq X$ is a choice set for ${\cal S}$ if for ...

**0**

votes

**1**answer

60 views

### “Popular” vertices in an infinite hypergraph

Let $\kappa$ be an infinite ordinal, and suppose $E\subseteq {\cal P}(\kappa)$ with $|E| > \kappa$. Let us call $x\in \kappa$ popular if $$|\{e\in E: x\in e\}| > \kappa.$$
If $\text{Pop}(\kappa)...

**3**

votes

**2**answers

130 views

### Known result about existence of $n$-vertex $k$-uniform $r$-hypergraphs?

Are there known results about $n,k,r$ such that $n$-vertex $k$-uniform $r$-regular hypergraphs exist? If this is too large a class of hypergraphs, what if $k=\tilde{\theta}(\sqrt{n})$? What if an ...

**2**

votes

**2**answers

126 views

### Small dense subsets in “Hausdorff” hypergraphs

Let $H=(V,E)$ be a hypergraph. We call it Hausdorff if for all $x\neq y \in V$ there are $e_1,e_2\in E$ with $e_1\cap e_2 = \emptyset$ such that $x\in e_1$ and $y\in e_2$. We say that $D\subseteq V$ ...

**1**

vote

**2**answers

106 views

### Infinite “$T_1$”- hypergraphs

Let $X$ be an infinite set, and let $E \subseteq {\cal P}(X)$ be a collection of subsets of $X$. We say that $E$ is $T_1$ (with respect to $X$) if for all $x\neq y\in X$ there is $e\in E$ with $x\in e$...

**3**

votes

**2**answers

129 views

### Coloring hypergraphs with no singleton intersections

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ ...

**4**

votes

**0**answers

109 views

### Infinite $3$-chromatic hypergraphs

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ ...

**2**

votes

**1**answer

85 views

### How to encode subgraphs as hyperedges

Hi i was reading a paper "Propagating Distributions on a Hypergraph by Dual Information Regularization by Koji Tsuda", and one section stood out to me.
hypergraphs have more flexibility
in ...

**1**

vote

**1**answer

50 views

### Inequality about the minimum vertex degree in $k$-uniform hypergraphs

Let $H=(V,E)$ be a $k$-uniform hypergraph with $n$ vertices, that is, $V:=V(H)$ is a $n$-element finite set of vertices and $E:=E(H)\subset\binom{V}{k}$ is a family of $k$-element subsets of $V$.
...

**5**

votes

**0**answers

110 views

### Edge-coloring number of a linear hypergraph

A linear hypergraph is a hypergraph $H=(V,E)$ such that
$|e|\geq 2$ for all $e\in E$,
$|e_1\cap e_2|\leq 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$.
An edge coloring of $H$ is a function $c:E\to ...

**2**

votes

**3**answers

249 views

### Non-isomorphic hypergraphs on $\omega$

Let $H_i = (V_i, E_i)$ be hypergraphs for $i=1,2$. Then we say that $H_1\cong H_2$ if there is a bijection $\varphi:V_1\to V_2$ such that $A\in E_1$ implies $\varphi(A) \in E_2$ and $B\in E_2$ implies ...

**6**

votes

**1**answer

258 views

### Is an $O(n^{d-1})$ bound known for the maximum number of edges in an ordered $n$-vertex hypergraph avoiding a fixed $d$-permutation hypergraph?

By a $d$-permutation hypergraph, I mean, for some fixed integer $k$, a $d$-uniform hypergraph on $[dk]$ with $k$ disjoint edges such that every edge has exactly one vertex from each of $\{1,\ldots,k\}$...

**1**

vote

**0**answers

53 views

### Non-projective linear hypergraphs

A linear hypergraph is a pair $\pi=(\{1,\ldots,n\}, L)$ where $n\in\mathbb{N}$, $n\geq 2$ and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \...

**2**

votes

**0**answers

86 views

### Hypergraphs with edge coloring number equalling number of vertices

A linear hypergraph is a pair $\pi=(\{1,\ldots,n\}, L)$ where $n\in\mathbb{N}$, $n\geq 2$ and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \...

**0**

votes

**0**answers

87 views

### Steiner-like systems with large edges and many intersections

Let $l\geq 3$ be an integer. Is there $n\in\mathbb{N}$ and a hypergraph $H=(\{1,\ldots,n\},E)$ with the following properties?
for all $e\in E$ we have $|e| \geq l$
$e_1\neq e_2 \in E \implies |e_1 \...

**2**

votes

**1**answer

617 views

### 3-Approximation Algorithm for 3-Hitting Set

I need to find a $3$-approximation algorithm for finding a $3$-hitting set.
The set-up is that I have a set $S$ and a family $\mathcal{F}$ of subsets of $S$, where each member of $\mathcal{F}$ ...

**1**

vote

**0**answers

170 views

### Which weighted directed hypergraphs have incidence matrix of full rank?

what are the necessary conditions for a weighted directed hypergraph to have an incidence matrix of full rank?
In this context, we can define the incidence matrix as follows:
Let $V = \{v_1,v_2,...,...

**0**

votes

**0**answers

85 views

### Shortest hyperpath algorithm in intuitionistic fuzzy hypergraphs

I was looking for an algorithm to calculate the shortest hyperpath in intuitionistic fuzzy hypergraphs and I found only this article (which propose two algorithms).
Are there any others algorithms ...

**1**

vote

**1**answer

49 views

### Cardinalities of saturated linear hypergraphs

A saturated linear hypergraph is a hypergraph $H=(V,E)$ such that
$|e|\geq 2$ for all $e\in E$,
$|e_1\cap e_2| = 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$, and
$|\{e\in E:v\in e\}| = 2.$
Let $E$...

**-2**

votes

**1**answer

70 views

### Complete and saturated linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that
$|e|\geq 2$ for all $e\in E$,
$|e_1\cap e_2|\leq 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$.
We call a linear hypergraph complete if there ...

**2**

votes

**3**answers

146 views

### Minimal number of edges for complete linear hypergraphs

A complete linear hypergraph is a hypergraph $H=(V,E)$ such that
$|e|\geq 2$ for all $e\in E$,
$|e_1\cap e_2|=1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$, and
for all $v\in V$ we have $|\{e\in E:v\...