# Questions tagged [hypergraph]

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

200 questions
Filter by
Sorted by
Tagged with
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$ ...
111 views

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 ...
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 ...
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$...
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?
153 views

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

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. ...
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 ...
49 views

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 ...
33 views

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