Questions tagged [hypergraph]
Hypergraphs are generalizations of graphs, where edges can be made of more than two vertices.
273
questions
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,\...
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 ...
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 ...
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 ...
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 ...
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} \...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ${\...
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 ...
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 ...
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$ ...
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 ...
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$ ...
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, ...
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 ...
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 ...
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\}$ ...