# Questions tagged [hypergraph]

Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.

200
questions

**3**

votes

**0**answers

59 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$ ...

**4**

votes

**1**answer

111 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,...

**15**

votes

**2**answers

628 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 ...

**3**

votes

**0**answers

80 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 ...

**7**

votes

**1**answer

374 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}.$$
(...

**3**

votes

**0**answers

102 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 ...

**2**

votes

**0**answers

45 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 ...

**4**

votes

**1**answer

158 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 ...

**3**

votes

**1**answer

163 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 ...

**1**

vote

**1**answer

83 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$ ...

**7**

votes

**1**answer

100 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 ...

**2**

votes

**1**answer

117 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 ...

**1**

vote

**1**answer

78 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 ...

**7**

votes

**0**answers

75 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 ...

**5**

votes

**0**answers

139 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 ...

**3**

votes

**1**answer

159 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: ...

**1**

vote

**0**answers

56 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 ...

**5**

votes

**2**answers

212 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 ...

**3**

votes

**1**answer

70 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$...

**2**

votes

**1**answer

228 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?

**3**

votes

**2**answers

153 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 $\...

**3**

votes

**1**answer

104 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$. ...

**6**

votes

**1**answer

262 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 \...

**0**

votes

**1**answer

40 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 ...

**1**

vote

**0**answers

59 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 ...

**2**

votes

**1**answer

83 views

### making a random uniform hypergraph linear

Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{...

**3**

votes

**1**answer

42 views

### $1$-factorizability for “complete” finite hypergraphs

Let $H=(V,E)$ be a hypergraph such that $V\neq \varnothing$ and $\varnothing \notin E$. A matching is a subset $M\subseteq E$ such that $m_1\neq m_2 \in M$ implies $m_1\cap m_2 = \varnothing$, and $M$ ...

**0**

votes

**0**answers

43 views

### Birkhoff's theorem for hypergraphs

Birkhoff's theorem says that, in a bipartite graph $G$ in which both sides have size $n$, any fractional matching of size $n$ can be presented as a convex combination of integral matchings of size $n$ ...

**3**

votes

**1**answer

68 views

### Hyper-degree sequences: How to count them and how to construct hyper-graphs from them?

From an answer to this question I have learned how to ask this question properly.
Consider a $k$-uniform hypergraph on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges)...

**4**

votes

**1**answer

264 views

### Does every maximal almost disjoint family have the same chromatic number?

If $H=(V,E)$ is a hypergraph such that $V\neq\varnothing\neq E$ and $|e| > 1$ for all $e\in E$, and $\kappa\neq\varnothing$ is a cardinal, we say that a map $c:V\to\kappa$ is a coloring if the ...

**2**

votes

**0**answers

80 views

### What characterizes the incidence matrix of a tripartite hypergraph?

The incidence matrix of a graph $G = (V,E)$ is a matrix with $|V|$ rows and $|E|$ columns, in which element $v,e$ is $1$ if node $v$ is incident to edge $e$, and $0$ otherwise.
In bipartite graphs, ...

**2**

votes

**0**answers

30 views

### Forbidden structures for generalized hypertree width

Generalized hypertree width is a tree-width-like parameter for hypergraphs, which plays an important role in the study of constraint satisfaction problems and related areas. For its more well-known ...

**3**

votes

**1**answer

106 views

### Weisfeiler-Lehman test for hypergraphs

The Weisfeiler-Lehman test for graph isomorphism is based on iterative graph recoloring and works for almost all graphs, in the probabilistic sense. If we extend the domain to general hypergraphs, ...

**2**

votes

**1**answer

97 views

### Isomorphic hypergraphs of dense sets of Hausdorff spaces

If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$ , we say that they are isomorphic if there is a bijection $f:V_1 \to V_2$ such that for all $e\subseteq V_1$ we have $e\in E_1$ if and only if $f(e)\...

**2**

votes

**0**answers

92 views

### Perfect matching in hypergraphs: tripartite, regular and unbalanced

In a balanced bipartite graph - where both sides have the same size - a sufficient condition for the existence of a perfect matching is that the graph is regular - all vertices have the same degree.
...

**2**

votes

**0**answers

57 views

### From fractional matching to integral matching in tripartite hypergraphs

Let $G = (X\cup Y, E)$ by a bipartite graph with $n = |X|\leq |Y|$.
A fractional matching is a function assigning a non-negative weight to every edge in $E$, such that the sum of weights near each ...

**0**

votes

**1**answer

49 views

### Maximum number of edges in “square” hypergraph

For any set $X$ and any cardinal $\kappa$, let $[X]^\kappa$ denote the subsets of $X$ having cardinality $\kappa$.
A linear hypergraph is a hypergraph such that for all $e\neq e_1 \in E$ we have $|e\...

**1**

vote

**2**answers

195 views

### What is a bipartite hypergraph?

Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs:
In the Wikipedia page Hypergraph, a ...

**4**

votes

**1**answer

104 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 ...

**0**

votes

**1**answer

76 views

### Maximum-weight perfect matching in a 3-regular, complete, 3-partite hypergraph

Let $H=(V, E)$ be a weighted hypergraph such that $V=A\cup B \cup C$, where $A,B,C$ are disjoint sets of size $n$, and $E=A\times B\times C$. In my particular case, $\forall e\in E$, $ wt(e)\in\{0,\pm ...

**0**

votes

**0**answers

49 views

### Hypergraph coloring in linear hypergraphs

Let $H=(V,E)$ be a hypergraph with $V\neq\varnothing$ and $E \neq \varnothing$ such that
for all $e\in E$ we have $|e|\geq 2$, and
for all $e\neq e_1 \in E$ we have $|e\cap e_1|\leq 1$.
Is there a ...

**1**

vote

**1**answer

33 views

### Chromatic self-maps on finite complete linear hypergraphs

Let $X\neq\varnothing$ be a set and let ${\cal E}\subseteq {\cal P}(X)\setminus\{\varnothing\}$ be a collection of non-empty subset. We say that a map $f: {\cal E}\to X$ is a chromatic self-map if
$f(...

**2**

votes

**1**answer

104 views

### Intersecting subsets of $\{1,\ldots,n\}$

Is there $n\in\mathbb{N}$ and a collection ${\cal C}$ of subsets of $\{1,\ldots,n\}$ with the following properties?
$|{\cal C}| = n$,
$|c| > 1$ for all $c\in {\cal C}$,
$c\neq d \in {\cal C} \...

**3**

votes

**2**answers

135 views

### Are complete regular linear hypergraphs on $\omega$ isomorphic?

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$ we have $$A\in E_1 \text{ if and only if } f(...

**-1**

votes

**1**answer

79 views

### Infinite complete linear hypergraphs with edges of different sizes

Is there an infinite cardinal $\kappa$ with a collection of subsets ${\cal E}$ of $\kappa$ with the following properties?
$\bigcup {\cal E} = \kappa$,
$e \neq f \in {\cal E}$ implies $|e \cap f|=1$
$|...

**4**

votes

**1**answer

267 views

### Simple way to calculate the eigenvalues of a $2 \times 2 \times 2$ tensor

I am working with hypergraphs. The various matrices associated with hypergraphs are hypermatrix or tensors. I am interested in spectral aspects. In particular, I want to find all the eigenvalues ...

**3**

votes

**0**answers

49 views

### Maximum partite subset of edges of a hypergraph

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if
$\bigcup{\frak P} = X$, and
$P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.
Let $H = (V,...

**4**

votes

**0**answers

150 views

### Does $\mathbb{R}$ have a partite subbase?

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if
$\bigcup{\frak P} = X$, and
$P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.
Let $H = (V,...

**4**

votes

**1**answer

171 views

### Turan numbers of r-partite hypergraphs

Let $H$ be a balanced $r$-partite $r$-uniform hypergraph with $nr$ vertices. (Each part of this hypergraph consists of $n$ vertices; every hyperedge has exactly one vertex in each part.) Denote a ...

**2**

votes

**0**answers

110 views

### 3-uniform hypergraphs and their circuit space

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...