Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

3
votes
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
2answers
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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.