Questions tagged [hypergraph]
Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
32
questions
0
votes
1
answer
184
views
Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?
A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for ...
47
votes
15
answers
28k
views
What are the applications of hypergraphs?
Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
4
votes
1
answer
240
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 ...
35
votes
3
answers
3k
views
Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?
Question
Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
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 ...
7
votes
1
answer
948
views
Strategies for bounding the spectral norm of a tensor?
Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by
$$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$
(...
7
votes
2
answers
541
views
Perfect matchings in certain classes of hypergraphs
While doing research I came unto the following problem:
Given a hypergraph $H$ which is $r$-partite, $r$-uniform (each edge contains exactly $r$ vertices), $k$-regular (each vertex is contained in ...
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 ...
4
votes
1
answer
137
views
Chromatic number of regular linear hypergraphs on $\omega$
For any cardinal $\alpha \in \omega\cup \{\omega\}$, let $[\omega]^\alpha$ denote the collection of subsets of $\omega$ having cardinality $\alpha$.
A linear hypergraph $H=(V,E)$ is a hypergraph such ...
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,...
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 ...
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
8
votes
1
answer
692
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\{\...
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 \...
7
votes
2
answers
315
views
Perfect matchings of a regular, uniform, partite hypergraph
This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
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$ ...
5
votes
1
answer
1k
views
Hypergraph Chromatic Number vs Degree, Clique-Size
For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
3
votes
1
answer
184
views
A sequence of cardinal characteristics constructed with hypergraph coloring
Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$.
A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: ...
3
votes
1
answer
74
views
Injective choice function for finite Fano planes
Let $H=(V,E)$ be a hypergraph that is a finite Fano plane, that is, $V$ is a finite set and $E$ has the following properties:
for $e_1\neq e_2\in E$ we have $|e_1|=|e_2|$, as well as $|e_1\cap e_2|=1$...
3
votes
1
answer
181
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
2
votes
4
answers
147
views
$k$-regular linear set systems
For any set $X$ and cardinal $\kappa$, we denote by
$\ [X]^\kappa :=\ \binom X\kappa\ $ the collection of subsets of $X$ having cardinality $\kappa$.
If $X$ is a set, we call a set system $E\subseteq {...
2
votes
1
answer
249
views
De Bruijn–Erdős theorem for hypergraphs
The De Bruijn–Erdős theorem states that when all finite subgraphs of a graph $G$ can be colored with $n$ colors, the same is true for the whole graph.
There is a natural notion of coloring for ...
2
votes
3
answers
223
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\...
2
votes
1
answer
140
views
Injective choice function for "lines" in an infinite cardinal
Let $\lambda$ be an infinite cardinal and suppose ${\cal L}$ is a collection of subsets of $\lambda$ such that
$|k| = \lambda$ for all $k\in {\cal L}$ and,
if $k_1\neq k_2\in {\cal L}$ then $|k_1\cap ...
2
votes
3
answers
308
views
Constructions of $2-(v,3,3)$-designs
I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
2
votes
3
answers
295
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 ...
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 ...
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 ...
1
vote
0
answers
101
views
On a combinatorial design inspired by a football (soccer) tournament
Real-world inspiration. My younger son was playing a micro football (soccer) tournament this afternoon with $3$ other friends. Let's label the $4$ kids $0,1,2,3$. They played $3$ matches:
$\{0,1\} \...
1
vote
1
answer
138
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
0
votes
0
answers
108
views
"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$
$\newcommand{Po}{{\cal P}(\omega)}$
$\newcommand{lh}{\leq_{\text{hom}}}$
If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...
0
votes
1
answer
45
views
Non-pencil infinite projective plane with edges of different cardinalities
A projective plane is a hypergraph $H=(V,E)$ such that
if $e_1\neq e_2 \in E$ then $|e_1\cap e_2| = 1$, and
for $v,w\in V$ there is $e\in E$ such that $\{v,w\}\subseteq e$.
Is there a projective ...