# All Questions

Tagged with graph-theory hypergraph

61
questions

**3**

votes

**1**answer

47 views

### Connected hypergraphs

We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:
for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. ...

**1**

vote

**0**answers

22 views

### Definition of k-partite hypergraph

I would like to know the standard definition of k-partite hypergraph.
There are two natural generalizations of k-partite graph to k-partite hypergraph:
1. For all edges e, any two vertices in e are ...

**1**

vote

**1**answer

39 views

### Induced subgraphs of the line graph of a dense linear hypergraph

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...

**0**

votes

**0**answers

59 views

### Helly vs Strong p-Helly Property of Hypergraphs

I am not clear about the difference between Helly and Strong p-Helly property. For example hypergraph
H(V, E), V = { 1,2,3 } and E = {(1,2), (2,3), (1,3)}
has non-empty set for each pair of ...

**1**

vote

**1**answer

49 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

55 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

45 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

109 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!)...

**6**

votes

**2**answers

161 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

175 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

32 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

77 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

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