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

learn more… | top users | synonyms

-4
votes
1answer
58 views

Resources to learn about hypergraphs [closed]

I am working on a project that is based on hyper graphs. Is there any resource that I could refer to understand the basics properties of hyper graphs ?
4
votes
3answers
94 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 ...
2
votes
1answer
93 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 ...
0
votes
1answer
30 views

Minimal covers of hypergraphs

Suppose that $H=(V,E)$ is a hypergraph, so $V\neq \emptyset$ is a set and $E$ is a collection of subsets of $V$. A subset $C\subseteq E$ is said to be a cover if any $v\in V$ is contained in some ...
5
votes
1answer
122 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 ...
0
votes
0answers
61 views

Covering a set in a hypergraph

I'm interested in counting the following. Consider a set $\{v_1,\dots,v_m\}$ of $m$ vertices in the complete $k$-uniform hypergraph on $n$ vertices where $m < k$. I want to know the number of ...
1
vote
1answer
49 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 ...
2
votes
1answer
119 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 ...
-4
votes
1answer
83 views

Survey on Hypergraph Theory [closed]

I want to learn about hypergraphs.Can anyone help me with some links, articles and surveys. Thanks
1
vote
1answer
88 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
1answer
80 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
2answers
306 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 ...
4
votes
1answer
69 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
1answer
89 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
0answers
110 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
1answer
46 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
87 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). ...
3
votes
0answers
56 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
44 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
66 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
393 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
0answers
125 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
330 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
156 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
239 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
472 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
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
1answer
221 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
61 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
163 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
202 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
346 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
236 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
160 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
539 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
1answer
326 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
245 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
77 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
363 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
294 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
169 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
329 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
0answers
933 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
634 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
454 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
354 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
419 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
175 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
718 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, ...
20
votes
12answers
7k 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 ...