# All Questions

Tagged with graph-theory hypergraph

57 questions

**1**

vote

**1**answer

46 views

### Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that
for $e\in E$ we have $|e|\geq 2$, and
if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.
An injective edge choice function of a linear ...

**5**

votes

**0**answers

48 views

### Consequences of Ramsey-numbers of hypergraphs

We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent ...

**0**

votes

**0**answers

44 views

### Multigraph Factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...

**2**

votes

**2**answers

101 views

### Does any long path in a planar graph contain one of O(n) k-tuple of vertices?

My question is a bit related to both the container method and shallow cell complexity.
Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!)...

**5**

votes

**2**answers

144 views

### What is a hypergraph minor?

Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...

**4**

votes

**1**answer

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

**0**

votes

**0**answers

23 views

### Hypergraph mapping's projection

I have been struggling quite a while with a question, which I suspect might have a simple answer to:
I have a Graph G = (X,E,Ψ) with E (hyperedge) being a family of subsets of X and Ψ being a mapping ...

**-1**

votes

**1**answer

75 views

### Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**1**

vote

**0**answers

31 views

### Is there an algorithm for this constrained Hypergraph optimization problem?

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...

**19**

votes

**3**answers

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

**0**

votes

**1**answer

55 views

### Standard names of two finitary properties of hypergraphs?

Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...

**1**

vote

**1**answer

58 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

**0**answers

86 views

### Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?

Definition. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in ...

**1**

vote

**1**answer

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

**6**

votes

**1**answer

197 views

### Complexity for calculating number of Perfect Matchings in k-regular hypergraph

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices).
...