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

learn more… | top users | synonyms

1
vote
1answer
25 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
0answers
78 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
0answers
48 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
1answer
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
1answer
59 views

Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
4
votes
2answers
324 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 ...
0
votes
0answers
80 views

dominating set in a r-uniform hypergraph

I'm trying to solve exercise 6.7 on page 150 in "Probability and computing-Randomized algorithms and probabilistic analysis" by Michael Mitzenmacher: A Hypergraph H is a pair of sets (V,E) where V ...
1
vote
0answers
116 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
1answer
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
2answers
151 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
1answer
195 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
5answers
450 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
1answer
123 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
1answer
179 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
0answers
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
1answer
152 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
1answer
188 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
3answers
314 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
0answers
214 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
0answers
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
1answer
459 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
1answer
275 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
1answer
221 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
0answers
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
1answer
313 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
1answer
267 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
0answers
160 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
3answers
320 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 ...
5
votes
0answers
758 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
1answer
547 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
1answer
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
0answers
324 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
1answer
398 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
1answer
168 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
0answers
631 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
2answers
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 ...