Questions tagged [hypergraph]
Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
275
questions
3
votes
0
answers
72
views
Weighted vertex coloring of hypergraphs
Let $G=(V,E)$ be a simple graph. Let $w$ be a non-negative, integer valued weight function on the vertex set. The chromatic number $\chi(G,w)$ of the vertex-weighted graph $(G,w)$ is defined to be ...
- 151
3
votes
2
answers
173
views
Does any long path in a planar graph contain one of O(n) k-tuple of vertices?
My question is a bit related to both the container method and shallow cell complexity.
Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!)...
- 18.4k
6
votes
2
answers
510
views
What is a hypergraph minor?
Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...
- 18.4k
5
votes
1
answer
348
views
Graphs with minimum degree $\delta(G)\lt\aleph_0$
Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...
- 11.9k
4
votes
1
answer
155
views
Are two "perfectly dense" hypergraphs on $\mathbb{N}$ necessarily isomorphic?
We say that a hypergraph $(\mathbb{N}, E)$ where $E\subseteq {\cal P}(\mathbb N)$ is perfectly dense if
$\mathbb{N}\notin E$,
all $e\in E$ are infinite,
$e_1, e_2 \in E$ implies $|e_1\cap e_2| = 1$,...
- 45.4k
2
votes
1
answer
89
views
$T_1$-spaces vs $T_1$-hypergraphs
Let us say that a hypergraph $H=(V,E)$ is $T_1$ if for $x\neq y$ there is $e\in E$ such that $e\cap\{x,y\} = \{x\}$.
Note that for any $T_1$-space $(X,\tau)$ the topology $\tau$ contains the ...
- 45.4k
0
votes
1
answer
70
views
Maximizing set systems with property $\mathbf{B}$
Let $X$ be an infinite set, and let ${\cal E}$ be a collection of non-empty subsets of $X$. We say that ${\cal E}$ has property $\mathbf{B}$ if there is $B\subseteq X$ such that $B\cap E\neq \emptyset$...
- 45.4k
4
votes
0
answers
66
views
Lower and upper (combinatorial) discrepancy
(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.)
The combinatorial discrepancy of a family $\mathcal F$ ...
- 18.4k
0
votes
1
answer
94
views
Coloring a complete regular hypergraph
For any set $X$ and positive integer $k$ denote by $[X]^k$ the set of subsets $S\subseteq X$ such that $|S|=k$.
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $...
- 45.4k
6
votes
1
answer
183
views
Chromatic number of a connected Hausdorff space
Let $(X,\tau)$ be a topological space such that $\tau$ contains no singleton. We say that a map $c:X\to \kappa$, where $\kappa$ is a cardinal, is a coloring for $(X,\tau)$, if for every $U\in \tau\...
- 45.4k
1
vote
1
answer
60
views
Hypergraph colorings with small fibers
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...
- 45.4k
0
votes
1
answer
105
views
Size of edge set of infinite hypergraphs with $\chi(H) = |V(G)|$
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...
- 45.4k
5
votes
1
answer
201
views
Is the category of hypergraphs cartesian-closed?
If $H_i = (V_i, E_i)$ for $i=1,2$ are hypergraphs then a map $f:V_1\to V_2$ is said to be a hypergraph homomorphism if $f(e_1)\in E_2$ for all $e_1\in E_1$. Hypergraphs together with hypergraph ...
- 45.4k
-1
votes
1
answer
84
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 ...
- 45.4k
1
vote
0
answers
36
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 = ...
- 133
3
votes
1
answer
125
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\...
- 45.4k
4
votes
1
answer
72
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 ...
- 45.4k
0
votes
1
answer
73
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]...
- 11
3
votes
1
answer
71
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$).
...
- 45.4k
20
votes
3
answers
968
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 ...
- 45.4k
2
votes
1
answer
109
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? ...
- 397
2
votes
1
answer
399
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,...,...
- 33
6
votes
0
answers
209
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 ...
- 22.9k
0
votes
1
answer
61
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,...
- 40.9k
3
votes
1
answer
254
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,...
- 45.4k
2
votes
1
answer
100
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$?
- 45.4k
5
votes
1
answer
203
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,585
3
votes
0
answers
61
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....
- 31
1
vote
2
answers
303
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 \...
- 45.4k
8
votes
1
answer
305
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, ...
- 663
1
vote
1
answer
83
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 ...
- 45.4k
1
vote
0
answers
94
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 ...
- 4,165
1
vote
1
answer
79
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 ...
- 45.4k
0
votes
1
answer
195
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 ...
- 103
4
votes
0
answers
111
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$ ...
- 909
6
votes
1
answer
347
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$ ...
- 909
6
votes
1
answer
502
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).
...
- 155
7
votes
2
answers
378
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 \...
- 45.4k
-2
votes
1
answer
90
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 ...
- 45.4k
0
votes
1
answer
190
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 ...
- 45.4k
2
votes
0
answers
50
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 ...
- 655
1
vote
1
answer
166
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 ...
- 45.4k
0
votes
1
answer
70
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)...
- 45.4k
4
votes
2
answers
248
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 ...
- 251
2
votes
2
answers
134
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$ ...
- 45.4k
1
vote
2
answers
109
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$...
- 45.4k
3
votes
2
answers
176
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$ ...
- 45.4k
4
votes
0
answers
116
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$ ...
- 45.4k
2
votes
1
answer
241
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 ...
- 121
1
vote
1
answer
64
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$.
...
- 139