Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
4
votes
1answer
102 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
59 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$?
4
votes
1answer
140 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
142 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
188 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
51 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
80 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
80 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
93 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
299 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
130 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
309 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
111 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
44 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
125 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
124 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
123 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
107 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
78 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
47 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
104 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 ...
1
vote
3answers
241 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
237 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
51 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
81 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
513 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
152 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
80 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
66 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
140 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
587 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
230 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
222 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
165 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.
0
votes
1answer
34 views
Maximal expansions of strongly minimal covers of hypergraphs
Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ (...
7
votes
1answer
150 views
Is there a Degenerate Dependency Local Lemma?
The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...
3
votes
0answers
82 views
Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?
What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
3
votes
3answers
132 views
Linear intersection number and vertex covering number
A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set 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 \in L$ then $|...
1
vote
1answer
110 views
Minimality condition in a certain class of hypergraphs
A hypergraph is a pair $H=(V,E)$ such that $V$ is a (possibly infinite) set and $E\subseteq \mathcal{P}(V)$. $C\subseteq E$ is said to be a cover if $\bigcup C = V$ and $C$is minimal if $C'\subseteq C$...
4
votes
1answer
158 views
Strongly minimal covers
Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$.
A cover $M\subseteq E$ is said to be strongly ...
