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.
