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

**3**

votes

**1**answer

60 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

774 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

38 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

233 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

81 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

174 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

67 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

165 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

49 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

144 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

194 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

52 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

82 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

58 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

81 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

95 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

304 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

141 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

311 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

117 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

131 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

57 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

128 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

128 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

79 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

48 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

106 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

244 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

250 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

52 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

84 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

86 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

525 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

160 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

81 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

142 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\...

**0**

votes

**1**answer

53 views

### Maximizing the chromatic number of regular hypergraphs

Let $H=(V,E)$ be a hypergraph, let $n\in\mathbb{N}$. A vertex coloring is a map $c: V\to \{1,\ldots, n\}$ such that for $v\neq w \in V$ we have $c(v)\neq c(w)$ whenever there is $e\in E$ such that $v, ...

**8**

votes

**1**answer

588 views

### Edge chromatic number of hypergraphs

This is question Selection problem in a collection of non-empty sets with a simplification in criterion 3.
Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\...

**2**

votes

**1**answer

232 views

### Proof that it's possible to colour all elements in set, that all subsets will be bicolored

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact).
=================
...

**9**

votes

**3**answers

234 views

### Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Let $G=(V,E)$ be a graph. Its (open) neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the (open) neighborhood of every vertex $v \in V$.
It seems that not ...

**5**

votes

**1**answer

225 views

### Algorithm for 2-coloring classes of 3-uniform hypergraphs

Hi all and thanks in advance for your efforts.
I'm interested in 2-coloring 3-uniform hypergraphs. I know that in general, the problem of deciding if a 3-uniform hypergraph is 2-colorable is NP-hard....

**4**

votes

**1**answer

168 views

### Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable?
Thanks in advance.