Questions tagged [hypergraph]

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

Filter by
Sorted by
Tagged with
6 votes
0 answers
300 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,\...
Andrew D. King's user avatar
5 votes
0 answers
178 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 ...
Henry Towsner's user avatar
1 vote
1 answer
1k 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 ...
Ankur's user avatar
  • 61
7 votes
1 answer
687 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 ...
Seva's user avatar
  • 22.8k
7 votes
2 answers
538 views

Perfect matchings in certain classes of hypergraphs

While doing research I came unto the following problem: Given a hypergraph $H$ which is $r$-partite, $r$-uniform (each edge contains exactly $r$ vertices), $k$-regular (each vertex is contained in ...
Pedro T. Lima's user avatar
6 votes
1 answer
223 views

A non-distinct system of representative edges

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
julkiewicz's user avatar
10 votes
2 answers
902 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 ...
Oliver Kullmann's user avatar
0 votes
1 answer
485 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 ...
koeservat's user avatar
3 votes
0 answers
212 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 ...
Niel de Beaudrap's user avatar
6 votes
3 answers
450 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 ...
domotorp's user avatar
  • 18.3k
8 votes
0 answers
2k 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$ ...
Florent Foucaud's user avatar
5 votes
1 answer
1k 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 ...
Dave Pritchard's user avatar
10 votes
1 answer
595 views

Are shift-chains two-colorable?

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 ${\...
domotorp's user avatar
  • 18.3k
6 votes
0 answers
848 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 ...
Dave Pritchard's user avatar
4 votes
1 answer
573 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 ...
Niel de Beaudrap's user avatar
35 votes
3 answers
3k views

Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
Chris Beck's user avatar
4 votes
1 answer
230 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 ...
Eric Price's user avatar
13 votes
1 answer
3k views

Is there a version of König's theorem for tripartite 3-graphs?

I would like to know if there exists a version of König's theorem for tripartite $3$-graphs. In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
tbg's user avatar
  • 131
8 votes
0 answers
1k 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, ...
Gwyn Whieldon's user avatar
6 votes
1 answer
2k views

Maximum bipartite graph (1,n) "matching"

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...
Karussell's user avatar
  • 161
44 votes
15 answers
28k views

What are the applications of hypergraphs?

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
9 votes
2 answers
2k 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 ...
Ryan Williams's user avatar
5 votes
2 answers
925 views

Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if $X$ is a finite set and $H$ is any family of subsets of $X$, in which every vertex occurs in at most $d$ sets of $H$, then there is a function $f\colon X\to\{1,-1\}$ ...
Boris Bukh's user avatar
  • 7,746

1 2 3 4 5
6