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

**4**

votes

**1**answer

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

**0**

votes

**1**answer

75 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

88 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

38 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

81 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

**0**answers

51 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

37 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

60 views

### Beck-Fiala for other discrepancies

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

**4**

votes

**2**answers

357 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

117 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

323 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).
...

**4**

votes

**2**answers

153 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

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

**11**

votes

**5**answers

460 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

124 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

189 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

58 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

157 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

192 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

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

**7**

votes

**0**answers

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

**5**

votes

**0**answers

158 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

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

**4**

votes

**1**answer

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

**4**

votes

**1**answer

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

**2**

votes

**0**answers

72 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}) ...

**6**

votes

**1**answer

330 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

272 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

162 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

324 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

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

**4**

votes

**1**answer

577 views

### Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...

**8**

votes

**1**answer

441 views

### Do Shift-chain have Property B?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.
For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.
A $k$-uniform hypergraph ...

**6**

votes

**0**answers

333 views

### Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...

**4**

votes

**1**answer

400 views

### Bounds on strong vertex colourings of regular hypergraphs?

What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H?
A regular hypergraph is one in which every vertex is contained in ...

**4**

votes

**1**answer

170 views

### Negative Association of Component Size in Random Hypergraph

I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d << k$ and $n = 4k d^2$ or so.
The hyperedges are placed independently uniformly at random. I would like to have a ...

**6**

votes

**0**answers

698 views

### Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...

**8**

votes

**2**answers

1k views

### A generalization of Boolean matrix multiplication for order-3 tensors

The Boolean matrix product of two 0-1 $n \times n$ matrices $A$ and $B$ is the matrix $C$ defined as
$$C[i,j] = \vee_{k=1}^n (A[i,k] \wedge B[k,j]).$$ If $A = B$ and the matrix is an adjacency matrix ...