MathOverflow

Questions tagged [hypergraph]

Ask Question

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

200 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
3
votes
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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 ...

1
2 3 4

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.