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

Questions tagged [hypergraph]

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

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