Questions tagged [hypergraph]
Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
225
questions
0
votes
0
answers
31
views
Cutsets and disjoint edge sets in graphs
If $H=(V,E)$ is a hypergraph then we say that $C\subseteq V$ is a cutset if $C\cap e \neq \emptyset$ for all $e\in E$. We set
$$\text{cut}(H) = \min\{|C|: C \text{ is a cutset of }H\}.$$ A subset $D\...
- 39.3k
1
vote
1
answer
134
views
"Lamp-switch set-up number" of $n$ [closed]
Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way.
Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{...
- 39.3k
4
votes
1
answer
100
views
Strongly minimal covers for clique hypergraphs of graphs
$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges.
One class of examples is obtained by taking a graph $G=(V,E)...
- 1,064
2
votes
1
answer
37
views
Maximal matchable set in hypergraph with finite edges
Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\...
- 39.3k
1
vote
1
answer
57
views
Edge sets on $\omega$ maximal with respect to chromatic number
If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$...
- 39.3k
3
votes
0
answers
161
views
Conjecture on connected hypergraphs
A hypergraph $H=(V,E)$ with $V$ non-empty is said to be connected if for all $S\subseteq V$ with $\emptyset \neq S \neq V$ there is $e\in E$ such that $e$ intersects both $S$ and $V\setminus S$.
Given ...
- 39.3k
0
votes
1
answer
41
views
Conflict-free coloring of linear hypergraphs on $\omega$
This question is motivated by considerations on conflict-free colorings, which arose while studying assignment problems for frequencies in cellular networks.
A hypergraph $H=(V,E)$ is said to be ...
- 39.3k
3
votes
0
answers
174
views
A form of Hadwiger's conjecture for hypergraphs
A hypergraph $H=(V,E)$ consists of a
set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define
$$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$
and call $(S, E|_S)$ the ...
- 39.3k
1
vote
1
answer
196
views
Chromatic number of duals of uniform hypergraphs with large edges
Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say that $H$ is $\kappa$-uniform if $|e|=\kappa$ for all $e\in E$.
If $X$ is a non-empty set, then a map $c:V\to X$ is said to be a ...
- 39.3k
1
vote
1
answer
117
views
Chromatic number and taking duals of hypergraphs
If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...
- 39.3k
1
vote
2
answers
67
views
Number of edges in $k$-uniform linear hypergraph
Let $3 \leq k < n \in \mathbb{N}$. By $[n]^k$ we denote the collection of the subsets of $n = \{0,\ldots,n-1\}$ that have size $k$. We say that a hypergraph $H=(n,E)$ is $k$-uniform if $E\subseteq [...
- 39.3k
2
votes
2
answers
74
views
Matching number in infinite hypergraphs
If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ ...
- 39.3k
4
votes
0
answers
60
views
Chromatic index of hypergraphs
A proper $k$-edge-coloring of a hypergraph $H$ is a mapping from $E(H)$ to a set of $k$ colors so that every pair of adjacent edges receives different colors. We say $H$ is $k$-edge-colorable if
$H$ ...
- 413
2
votes
1
answer
110
views
3-uniform tetrahedron-free hypergraph on seven vertices
My problem concerns 3-uniform hypergraphs. Let $f(n)$ be the maximal number of edges in a 3-uniform hypergraph such that no four edges form a "tetrahedron", i.e., four edges that join the ...
- 2,265
0
votes
1
answer
50
views
Are strongly complete regular linear hypergraphs on $\omega$ isomorphic?
This is a related question to an older one.
If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ ...
- 39.3k
1
vote
1
answer
104
views
Cardinalities of maximal linear $k$-subsets of $n = \{0,\ldots,n-1\}$
We consider any non-negative integer $n$ as a cardinal, so $0 = \emptyset$, and $n=\{0,\ldots,n-1\}$ for positive $n$. Given $n,k\in \mathbb{N}$, let $[n]^k$ denote the collection of $k$-element ...
- 39.3k
-1
votes
1
answer
70
views
Chromatic number of $(n, [n]^k)$
If $n\in\mathbb{N}$ is a non-negative integer, we consider it as a cardinal, so $n = \{0, \ldots, n-1\}$. If $X$ is a set, and $\kappa$ is a cardinal, we let $[X]^\kappa$ be the collection of subsets ...
- 39.3k
1
vote
1
answer
74
views
Self-dual hypergraph on $\omega$
Let $H=(V,E)$ be a hypergraph. For $v\in V$ we let $v^* = \{e\in E:v\in e\}$. We define the dual of $H$ by $H^*= (E, V^*)$ where $V^* = \{v^*: v\in V\}$. We say that a $H$ is self-dual if $H \cong H^*$...
- 39.3k
2
votes
0
answers
44
views
Number of nonisomorphic weighted hypergraphs of certain type
Let $G=(V,E)$ be an unlabeled simple hypergraph with weighted vertices and given properties:
$|v|⩾max(d(v);\;3)\;∀v∈V$, where $|v|$ denotes weight of vertice $v$ and $d(v):=\#(e:\;v∈e)$ - number of ...
- 31
0
votes
1
answer
39
views
Discrepancy of chromatic number and independent covering number for $k$-regular hypergraphs
If $H=(V,E)$ is a hypergraph and $\kappa \neq \emptyset$ is a cardinal, then a map $c:V\to\kappa$ is called a coloring if the restriction $c\restriction_e$ is non-constant for all $e\in E$ with $|e|\...
- 39.3k
2
votes
1
answer
45
views
Summable hypergraphs
A hypergraph $H=(V,E)$ is sane if $V$ is finite, $E \neq \emptyset$, and $\emptyset \notin E$, and $e\not\subseteq e'$ whenever $e\neq e' \in E$. Moreover, we call $H$ summable if there is a map $f:V\...
- 39.3k
1
vote
1
answer
82
views
Large chromatic number in hypergraphs with large edges
Let $H=(V,E)$ be a hypergraph. If $\kappa \neq \emptyset$ is a cardinal, we call a map $c:V\to \kappa$ a coloring if for each $e\in E$ with $|e|>1$ the restriction $c\restriction_e$ is non-constant....
- 39.3k
1
vote
2
answers
242
views
"Coloring" the greatest common divisor relation
Let $N_+$ denote the set of positive integers. Let $E$ be the collection of all finite $A\subseteq \mathbb{N}_+$ such that $|A|\geq 3$ and $\min(A)$ is the greatest common divisor of $A\setminus\{\min(...
- 39.3k
2
votes
0
answers
86
views
Shrinking a hypergraph to a graph with identical chromatic number
Let $H=(V,E)$ be a hypergraph. A coloring is a map $c:V\to \kappa$ where $\kappa\neq \emptyset$ is a cardinal, and the restriction $c\restriction_e:e\to \kappa$ is non-constant for every $e\in E$ with ...
- 39.3k
3
votes
1
answer
68
views
Turán density of an unbalanced complete $r$-partite $r$-graph
In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following:
Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ ...
- 131
3
votes
0
answers
61
views
On a connectivity property of set systems
Let $X\neq \emptyset$ be a set and let ${\cal A}\subseteq {\cal P}(X)$ with $\bigcup {\cal A}=X$. We say that $S\subseteq X$ is indivisible if for all $T\subseteq S$ with $\emptyset \neq T \neq S$ ...
- 39.3k
3
votes
1
answer
122
views
Coloring the uncountable Lebesgue-measurable sets of $\mathbb{R}$
A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$, that is, $E$ consists of subsets of $V$ of arbitrary size. Obviously, a graph is a special kind of hypergraph.
Let $H=(V,...
- 39.3k
15
votes
2
answers
703
views
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
- 161
3
votes
0
answers
88
views
When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?
This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
- 143
7
votes
1
answer
578
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}.$$
(...
- 16.7k
3
votes
0
answers
123
views
Spectral norm and "operator norm" for hypergraphs
Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
- 16.7k
4
votes
3
answers
305
views
Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?
I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
- 43
4
votes
1
answer
178
views
Seven Bridges of Königsberg for hypergraphs
I am teaching a course involving hypergraphs. I would like to have a physical analogy/motivating problem for hypergraphs similarly to how the Seven Bridges of Königsberg motivate graphs. Can you help ...
- 41
3
votes
1
answer
254
views
Chromatic number of maximal linear $k$-regular hypergraphs on $\omega$
For any integer $k>1$ we say a hypergraph $H=(\omega,E)$ where $E\subseteq {\cal P}(\omega)$ is $k$-regular if $|e|=k$ for all $e\in E$. Moreover, we say $H$ is linear if $|e_1\cap e_2|\leq 1$ for ...
- 39.3k
1
vote
1
answer
88
views
Fano-like planes on $\omega$
We call $E\subseteq {\cal P}(\omega)$ a Fano-like plane if
for all $x,y\in \omega$ there is $e\in E$ with $\{x,y\}\subseteq e$,
whenever $e_1\neq e_2\in E$ we have $|e_1\cap e_2|=1$, and
$|e|>1$ ...
- 39.3k
6
votes
1
answer
105
views
Tameable hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$.
We say that $H$ is tameable if every independent set is contained in a maximal ...
- 39.3k
2
votes
1
answer
130
views
Chromatic number of rainbow hypergraphs
Let $H=(V,E)$ be a hypergraph, and $\kappa$ be a cardinal. We say that a map $c:V \to \kappa$ is a coloring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ and $|e|\geq 2$. The ...
- 39.3k
1
vote
1
answer
83
views
Minimizing the set of monochromatic edges
For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.
Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
- 39.3k
7
votes
0
answers
85
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 7,217
4
votes
0
answers
161
views
The list reaping number?
My question is inspired by a question of Dominic van der Zypen. Let $[\omega]^\omega$ denote the set of all infinite subsets of $\omega$.
The reaping number, denoted by $\mathfrak r$, is the minimum ...
- 8,573
3
votes
1
answer
165
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: ...
- 39.3k
1
vote
0
answers
58
views
Generalization of Moore graphs -- not geometries
I was thinking about the following problem: Suppose you have a $k$-uniform hyper graph (simplicial complex of dimension $k$) with a complete $(k-1)$-skeleton, and some form of regularity (e.g. every ...
- 433
5
votes
2
answers
233
views
Triangle coloring in random graph
Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...
- 491
3
votes
1
answer
72
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$...
- 39.3k
3
votes
1
answer
314
views
VC dimension of vector spaces
Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension?
Could someone please provide references for this question?
- 397
4
votes
2
answers
201
views
Relationship between minimum vertex cover and matching width
Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$).
Question: Is $\...
- 1,461
3
votes
1
answer
108
views
Can every number be realised as the chromatic number of a countable hypergraph?
If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal,we say a map $c:V\to\kappa$ is a coloring if the restriction $c\restriction_e$ of $c$ to $e$ is non-constant whenever $e\in E$ and $|e|>1$. ...
- 39.3k
6
votes
1
answer
264
views
Singular cardinal $\kappa$ with projective plane such that all edges have cardinality $<\kappa$
Is there an infinite singular cardinal $\kappa$ such that there is a set $E\subseteq{\cal P}(\kappa)$ with the following properties?
$|e| < \kappa$ for all $e\in E$,
whenever $\alpha\neq\beta\in \...
- 39.3k
0
votes
1
answer
42
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 ...
- 39.3k
1
vote
0
answers
60
views
$1$-factorizability for linear hypergraphs with infinite edges on $\omega$
Let $H=(V,E)$ be a hypergraph. We say that $M\subseteq E$ is a matching if the members of $M$ are pairwise disjoint, and $M$ is said to be perfect if $\bigcup M = E$. Moreover, $H$ is $1$-factorizable ...
- 39.3k