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

**0**

votes

**0**answers

24 views

### Tree decompositions in linear hypergraphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a finite set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ ...

**8**

votes

**1**answer

545 views

### Edge chromatic number of hypergraphs

This is question Selection problem in a collection of non-empty sets with a simplification in criterion 3.
Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\...

**2**

votes

**1**answer

216 views

### Proof that it's possible to colour all elements in set, that all subsets will be bicolored

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact).
=================
...

**8**

votes

**3**answers

166 views

### Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Let $G=(V,E)$ be a graph. Its (open) neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the (open) neighborhood of every vertex $v \in V$.
It seems that not ...

**5**

votes

**1**answer

82 views

### Algorithm for 2-coloring classes of 3-uniform hypergraphs

Hi all and thanks in advance for your efforts.
I'm interested in 2-coloring 3-uniform hypergraphs. I know that in general, the problem of deciding if a 3-uniform hypergraph is 2-colorable is NP-hard....

**4**

votes

**1**answer

120 views

### Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable?
Thanks in advance.

**0**

votes

**1**answer

29 views

### Maximal expansions of strongly minimal covers of hypergraphs

Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ (...

**7**

votes

**1**answer

136 views

### Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...

**3**

votes

**0**answers

66 views

### Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?

**3**

votes

**3**answers

116 views

### Linear intersection number and vertex covering number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then $|...

**1**

vote

**1**answer

109 views

### Minimality condition in a certain class of hypergraphs

A hypergraph is a pair $H=(V,E)$ such that $V$ is a (possibly infinite) set and $E\subseteq \mathcal{P}(V)$. $C\subseteq E$ is said to be a cover if $\bigcup C = V$ and $C$is minimal if $C'\subseteq C$...

**4**

votes

**1**answer

137 views

### Strongly minimal covers

Let $H=(V,E)$ be a hypergraph, that is $V$ is a set and $E\subseteq \mathcal{P}(V)$. We say that $C\subseteq E$ is a cover of $H$ if $\bigcup C = V$.
A cover $M\subseteq E$ is said to be strongly ...

**1**

vote

**0**answers

95 views

### Optimal tiling for a collection of partitions

I'm interested in a possible generalization of Tiling relation on the set of partitions (the question has only been partially answered).
Let $x$ be an infinite set and let $\text{Part}(x)$ be the ...

**0**

votes

**1**answer

60 views

### Minimal hypergraphs with respect to separation

Let $H = (V, E)$ be a hypergraph, that is $V$ is a set and $E \subseteq \mathcal{P}(V)$. We say that $H$ is $T_1$ if for $v\neq w$ there are $e_v, e_w \in E$ such that $v\in e_v, w\notin e_v, w\in e_w,...

**2**

votes

**1**answer

244 views

### Maximum number of hyperedges on a hypergraph without a spanning tree

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges ...

**1**

vote

**1**answer

109 views

### Number of points in an intersecting linear hypergraph

I first asked the question below at math.stackexchange.com ( http://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...

**2**

votes

**1**answer

96 views

### When does a hypergraph represent maximal independent sets?

Let $G = (V,E)$ be a simple graph. Then, we can view the set of maximal independent sets (or the set of maximal cliques) as a hypergraph $H = (V, E')$. This is quite a useful device when connecting ...

**4**

votes

**2**answers

331 views

### Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}...

**4**

votes

**1**answer

85 views

### Is it true that every hypergraph with a large “semi-shattered” set has large VC dimension?

Given a hypergraph $H=(V,E)$ and a set $X\subseteq V$ of vertices, let $int(X)$ be the number of distinct intersections of edges with $X$, i.e.
$$int(X)=|\{S\subseteq X, \exists e\in E, e\cap X=S\}|.$...

**0**

votes

**1**answer

115 views

### Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...

**4**

votes

**0**answers

140 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**1**

vote

**1**answer

53 views

### a class of directed hypergraphs

I am interested in a certain class of directed hypergraphs, more precisely in the class of those hypergraphs each of whose hyperedges contain an even number of nodes (not necessarily the same even ...

**2**

votes

**0**answers

103 views

### Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...

**2**

votes

**3**answers

234 views

### Constructions of $2-(v,3,3)$-designs

I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...

**3**

votes

**0**answers

64 views

### Perfect Matching for Edge-transitive Hypergraphs

I'm new to this subject, but I've noticed that a lot of work has been done on perfect matching in k-uniform hypergraphs. I'm curious to know if there are any results on perfect matching in the more ...

**1**

vote

**1**answer

48 views

### How to compute hereditary discrepancy

I want to compute exactly the hereditary discrepancy of a small (on up to 20 points) set system - is there an efficient way to do it? Brute force search over the discrepancies of all subsystems seems ...

**1**

vote

**1**answer

71 views

### Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?

**5**

votes

**2**answers

717 views

### Motivation for Frankl's conjecture?

Frankl's conjecture, open since 1979, says that if $F$ is a union-closed family of subsets of $X$, then there is some $x \in X$ such that $x$ appears in at least half the sets in $F$.
What was the ...

**1**

vote

**0**answers

133 views

### regular hyper graph construction

Is there any algorithm to generate 3-uniform k-regular hypergraph with n vertices?? Any help is appreciated. Thanks.

**2**

votes

**1**answer

336 views

### small hyperworlds ?

The theory of random graphs, after the pioneering classic work of Erdős & Rényi, has come to prominence with many further refinements, most notably the small world theory (Barabási, Watts, etc).
...

**5**

votes

**2**answers

196 views

### Bipartiteness criterion

A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that ...

**4**

votes

**1**answer

314 views

### 2-Coloring a planar hypergraph

Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a ...

**12**

votes

**5**answers

504 views

### Intersecting 4-sets

Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements?
To see that $N$ is achievable, ...

**2**

votes

**1**answer

128 views

### Property of cube hypergraph Q(n,n)

The set of vertices of $Q(d,n)$ is $\{0,1,\ldots,n-1\}^d$ and every edge is formed by all vertices having $d-1$ coordinates fixed and the last one getting all possible values (so it has $dn^{d-1}$ ...

**0**

votes

**1**answer

253 views

### hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...

**0**

votes

**0**answers

65 views

### products/factoring of two hypergraphs with same vertex set?

all the basic products for graphs have been extended to hypergraphs[1].
is there a concept of a product of hypergraphs with the same vertex set? has this been studied?
normally the hypergraph ...

**2**

votes

**1**answer

180 views

### matchings in hypergraphs

I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform ...

**6**

votes

**1**answer

235 views

### Realiziability of hypergraphs as link (multi)sets of ordinary graphs

I have a question about hypergraphs that I hope some combinatorics/graph theory experts can answer. The motivation for this question is group-theoretic and comes from the study of a certain space of ...

**1**

vote

**3**answers

397 views

### Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1

I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example,
For example, the maximum value of $xy^...

**7**

votes

**0**answers

248 views

### A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.
The setup is as follows. We have a vertex set partitioned in to sets $V_1,\...

**5**

votes

**0**answers

167 views

### Small Configurations in Random Hypergraphs

I have a somewhat technical question regarding the distribution of small hypergraphs in randomly chosen hypergraphs. (My hope is that this is something that can be done using standard ideas about ...

**1**

vote

**1**answer

732 views

### k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide.
It is well known that for $k\geq 3$ finding ...

**5**

votes

**1**answer

386 views

### Perfect matching in a vertex-transitive hypergraph

In connection with this MO problem, I wonder whether the hypergraph in
question was actually vertex-transitive. And so, as a natural variation (and,
perhaps, a refinement):
If the vertex set of a ...

**5**

votes

**1**answer

290 views

### Perfect matchings in certain classes of hypergraphs

While doing research I came unto the following problem:
Given a hypergraph $H$ $r-partite$, $r-uniform$ (a r-graph, each edge contains r vertices), >$k- regular$ (all vertices have regular degree)...

**2**

votes

**0**answers

87 views

### A non-distinct system of representative edges.

I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) $...

**7**

votes

**1**answer

419 views

### The category of hypergraphs as a topos

It seems known that the category of hypergraphs is a topos.
I am looking for any reference here, or just a statement of this in the literature,
but can't find anything. There is one paper
A ...

**0**

votes

**1**answer

317 views

### Maximum number of hyperedges in a directed hypergraph

I need a formula for maximum number of hyperedges that a directed hypergraph with n vertices can have. Following point is an unresolved issues for me and it keeps coming back to my mind:
There are ...

**3**

votes

**0**answers

181 views

### Unique structures in a class of connected directed hypergraphs

Edit: The problem has been slightly revised, as I discovered that one of the questions I asked has an answer in the negative.
I'm working in a setting involving constraints on a system described by a ...

**3**

votes

**3**answers

343 views

### Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem.
Suppose we have a ...

**6**

votes

**0**answers

1k views

### What is the best lower bound for the domination number in regular graphs of girth 5?

The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$...