Questions tagged [hypergraphs]

Use this tag for questions about *hypergraphs*, i.e. generalizations of graphs in *graph theory*, in which edges are allowed to be arbitrary subsets of vertices, instead of just pairs.

0
votes
0answers
8 views

Measure of overlap between hyperedges in a hypergraph

Given a hypergraph $H = (V,E)$, does the quantity $\max_{e\in E}\left|e\cap \bigcup_{e'\in E\setminus \{e\}}e'\right|$, i.e., the maximum number of vertices shared between one hyperedge and all the ...
1
vote
0answers
22 views

How to construct conceptual models for graphs?

Construct conceptual models for the following types of graphs, using either ORM (Object-Role Modeling), ER (Entity-Relationship), or UML Class Diagrams: Directed graphs consist of nodes and directed ...
1
vote
0answers
27 views

Is there a sufficiently large vertex set in a 3-uniform hypergraph, which satisfies the following condition?

Suppose $\mathcal{H}=(V,\mathcal{E})$ is a $3$-uniform hypergraph on $n$ vertices, such that for any non-empty vertex set $S\subseteq V$ with $|S|\le t$ (where $(t<n)$), there is a $v\in S$ and an ...
0
votes
0answers
30 views

Polynomial-time algorithm for finding a loose cycle of fixed length in 3-uniform hypergraph

Suppose that $\mathcal{H}$ is a $3$-uniform hypergraph on $n$ vertices, and suppose that $m \geq 5$ and $n \geq 150m^2$. I am interested in designing a simple polynomial-time algorithm that, given $\...
2
votes
1answer
21 views

Number of unlabeled hypergraphs (A003180)

I'm looking for the number of unlabeled hypergraphs on n nodes and stumbled upon the comments of A003180 in OEIS. Can somebody please explain to me how that sequence relates to the number of unlabeled ...
1
vote
1answer
33 views

Proving Szemerédi's Theorem using the Simplex Removal Lemma for $k$-Uniform Hypergraphs.

Let $X$ be a set of $n$ vertices, and let $H$ be a hypergraph with vertex set £X£. Call $H$ a $k$-uniform hypergraph if all hyperedges of $H$ are subsets of $X$ of size $k$. Given a $k$-uniform ...
0
votes
0answers
20 views

Orthogonal Hypergraphs

Two hypergraphs $(V,E_1)$ and $(V,E_2)$ are said to be orthogonal if $E_1$ and $E_2$ are partitions of $V$ and the graph induced by $E_1$ and $E_2$ is acyclic and connected (ACC). Is there any ...
0
votes
0answers
10 views

Lower bound for matchings hypergraphs

I found a lower bound on matchings in hypergraphs in Pikhurkos paper: Perfect Matchings and $K^3_4$-Tilings in Hypergraphs of Large Codegree The bound is obtained by the following construction. We ...
3
votes
1answer
65 views

Bruhat-Tits Building of $PGL_3$: What does it look like?

I am very new to this topic, and my background is mostly in graph theory and basic algebra. What I want for now is to understand the structure of the dimension $2$ complex $\mathcal{B}(PGL_3(K))$ ...
0
votes
1answer
39 views

Proving full rank of a special type of a (0,1,2)-integer matrices

My question arise at the consideration of Newton polytopes. In that context I consider integer matrices $ A =(a_{ij})\in \mathbb{Z}^{(n+1) \times N} $ with $n+1 \leq N$ having the following ...
0
votes
1answer
67 views

What is the difference between matriods and hypergraphs?

Matroids have a more complicated definition but it looks to me like they might be equivalent. I would like to know exactly what the difference is, if any.
0
votes
1answer
31 views

Intersecting r-families with any two intersects in more than s elements.

There is a well-known fact that if $F$ is a family of $r$-subsets of an $n$-set no two of which intersect in exactly $s$ elements then $\vert F \vert \leq n^{\max\{s, r-s-1\}}$. But are there any ...
0
votes
0answers
31 views

Maximum Hitting Set of k-uniform Hypergraphs in Planar Graphs

I'm stuck with a problem and wonder whether you can help me. I guess the biggest problem is that I don't even know what I have to google for to find information about my problem. I'll try to explain ...
1
vote
0answers
68 views

Is $k$-rainbow coloring of a hypergraph NP-complete or not?

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. The problem is also called "polychromatic coloring" Is $k$-...
1
vote
1answer
33 views

Greedy coloring of uniform hyperhraphs

I'm reading this paper and I have a (simple) question about the way the writer uses one of its definitions. Definition 1: We say that $A \in E$ precedes $B \in E$ if the last vertex of $A$ becomes ...
0
votes
3answers
75 views

What is the prerequisit to studying spectral graph theory and hyper graphs? If one knows only the basics of graph theory

Can anyone suggest to me some books to learn spectral graph theory, hyper graph theory, and tensors used to study hyper graphs please? Preferribly books for beginners and then some books for advanced ...
1
vote
0answers
24 views

Densest hypergraph with bounded vertex degree.

Given integer $m$, what is the maximal number $d$, such that there exists a hypergraph with vertices of degree at most $d$, and the number of hyperedges is $d \cdot m \cdot const$? Using k-uniform ...
1
vote
1answer
22 views

Is L(H) = L(G) :: Is line graph of a hypergraph is also a line graph of a graph ??

The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph $\{E_1,...E_m\}$, with two hyperedges adjacent when they have a nonempty intersection. My ...
0
votes
1answer
36 views

What the meaning of “vertices induce hyperedges” in hypergraphs?

I don't understand what's the meaning of the word "induce" regrading hypergraphs. For example, "3 vertices induce 2 hyperedges". I would be glad if you could draw it and explain the meaning of the ...
3
votes
2answers
661 views

Example of hypergraph

Definition: A hypergraph $\Gamma=(V,\mathcal{E})$ is a set of vertices $V$ and a collection $\mathcal{E}$ of subsets of $V$ such that for every $E\in \mathcal{E}$, we have $|E|\geq 2$. The members of $...
2
votes
0answers
66 views

Edge-to-edge incidence structure of a graph

The Incidence matrix of a graph $G=(V,E)$ with $n=|V|$ numbered vertices $v_i$ and $m=|E|$ numbered edges $e_j$ is defined as the $n\times m$-matrix $M=(M_{ij})$ defined by $$ M_{ij}=\begin{cases}1 &...
1
vote
0answers
71 views

Random Independent set in 3-uniform hypergraph

What is the maximum size of an independent set in a 3-uniform hypergraph if we choose it randomly from the set of vertices of the hypergraph? Is there any reference/idea to this problem? Thanks in ...
1
vote
0answers
31 views

How to check if a separating system is minimal?

Let $\mathcal{H}$ be a minimal strongly separating system on a base set of size 20. Prove that $\mathcal{H}$ is a Sperner-system. Let $\mathcal{H}$ be a minimal strongly separating system on a base ...
1
vote
1answer
268 views

Independent set in $3$-uniform hypergraph

Suppose $H$ is a $3$-uniform hypergraph such that each pair of vertices contained in at most one hyperedge. Let $\alpha(H)$ be the maximum independent set of $H.$ Independent set is a subset of ...
0
votes
1answer
46 views

Expected number of multipled edges multihypergraph

I have a graph G of n vertices and with a k-list color assignment for each vertex out of $\sigma$ colors. If a choose at random all k colors for each list assignment I can model this with a k-uniform ...
0
votes
0answers
12 views

Show the existence of a set $F'$, such that $F \subseteq F'$ and $|F'|=2^{n-1}$!

$F\subseteq2^{[n]}$ and it has no disjoint elements in it. Show that exists an $F'\supseteq F$, such that $F'$ still has no disjoint elements and $|F'|=2^{n-1}$! I tried to construct $F'$ of $F$ ...
0
votes
1answer
89 views

what is hyper-tournament?

I know the definition of the tournament ( a directed graph obtained after assigning direction to edges of the complete graph). I tried on search on internet did not get anything. Question: What is ...
1
vote
0answers
19 views

Modelling distribution of nodes' neighbours in weighted networks

I have weighted networks where weights are cosine similarities values: they are computed in function of nodes' degrees and the intersection of common neighbours. Suppose this object is a model to ...
0
votes
1answer
103 views

How many hyperedges are in a (k, r) regular hypergraph?

I'm trying to write an algorithm to produce random $r$-regular $k$-uniform hypergraphs, the representation I am interested in is the incidence matrix. I've done this for the simpler case of a regular ...
0
votes
1answer
38 views

Show that for each $2<p<q<k$, $Q_k$ has a cycle of length $2^p+2^q$.

Let $Q_k$ be the $k$-hypercube. Assume that $Q_k$ has a Hamiltian cycle for each $k \geq 2$. Assume that $ 4 \leq k$. Show that for each $ 2 \leq p < q < k$, $Q_k$ has a cycle of length $2^p + 2^...
2
votes
0answers
199 views

Hypergraph examples for laymen

When I try and explain graph theory to my non-mathematician friends, I usually resort to motivating the idea through things like computer networks or neurons connected by synapses, but I don't have a ...
1
vote
0answers
26 views

Counting xyz-graphs in $\mathbb{Z}_n^3$

This is a followup question to: https://cstheory.stackexchange.com/questions/38462/lower-bound-on-the-largest-restrained-cubic-subset How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote ...
1
vote
0answers
41 views

Largest simple cycle in a 3-uniform tripartite hypergraph

Given a 3-uniform tripartite hypergraph G(n,m,k), we define a simple cycle to be any set of edges such that each set of two points within every hyperedge is contained in exactly two hyperedges, and ...
1
vote
0answers
53 views

How to encode subgraphs as hyperedges

Hi i was reading a paper "Propagating Distributions on a Hypergraph by Dual Information Regularization by Koji Tsuda", and one section stood out to me. hypergraphs have more flexibility in ...
1
vote
1answer
32 views

Is Steiner Triple System Always Regular?

I know that there exists $S(2,3,n)$, when $n\equiv 1,3\mod 6$. $S(2,3,7)$ is the Fano plane and $S(2,3,9)$ is an affine plane. These two examples are in fact both regular hypergraphs, i.e. every ...
1
vote
0answers
111 views

On the relation between eulerian graph and eulerian hypergraph?

Definition The 2-section of a hypergraph $H$, denoted by $[H]_2$, is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge. A ...
0
votes
0answers
90 views

Projective plane of uniformity 4

I was asked to construct a 4-uniform projective plane (meaning, a 4-uniform hypergraph that every two vertices belong to a single edge, and every two edges intersect in a single vertex). I managed to ...
4
votes
1answer
186 views

Is Hyper-graph Isomorphism preserve the size of edges or Rank of Hyper-graph?

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices. A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain ...
0
votes
1answer
75 views

Lower bound on transversal number of a specific hypergraph

Let $d\geq 2$ be an integer. I will define a hypergraph $H=(V,E)$ as follows. The vertex set is the set of all binary words of length $d$, i.e., $V=\{0,1\}^d$. The edges are sets of vertices that have ...
1
vote
1answer
69 views

Coloring 2-Intersecting Hypergraphs

I have some problem to understand a paper, this paper about "Coloring 2-Intersecting Hypergraphs. A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. In page 2 ...
1
vote
1answer
22 views

Hypergraph with the property that for any two edges $F_1, F_2 \in \mathcal F, |F_1 ∩ F_2 | ≥ 2$ is 2-colourable

Let $\mathcal F$ be a hypergraph with the property that for any two edges $F_1, F_2 \in \mathcal F, |F_1 ∩ F_2 | ≥ 2$. Prove that $\mathcal F$ is two-colourable. I have no idea to prove the claim. ...
1
vote
0answers
48 views

Which weighted directed hypergraphs have incidence matrix of full rank?

what are the necessary conditions for a weighted directed hypergraph to have an incidence matrix of full rank? This question is a generalization of this one: https://mathoverflow.net/questions/5553/...
1
vote
0answers
42 views

Online software to manipulate hypergraphs

There are many software systems around working with graphs, but is there anything (preferably publically available / online) to handle hypergraphs? Thanks!
1
vote
0answers
39 views

Complete linear hypergraph on $n$ points

A complete linear hypergraph is a hypergraph $H=(V,E)$ such that if $e_1, e_2\in E$ then $|e_1\cap e_2|=1$. Let $n\geq 3$. Can we pick $E\subseteq {\cal P}(\{1,\ldots, n\})$ such that $(\{1,\ldots, ...
2
votes
1answer
69 views

acyclic decomposition of hypergraphs

The following is from the paper Arboricity: An acyclic hypergraph decomposition problem motivated by database theory by Yeow Meng Chee, Lijun Ji, Andrew Lim, Anthony K.H. Tung: Question: For an ...
2
votes
1answer
49 views

Find a hypergraph such that $|e|$ even, $|e\cap f|$ odd, and $|E|>|V|$

Here is a problem I have been working on (it comes from the standard "odd-town" problem. The idea is to show that the analogy for "even-town" doesn't work). Find a hypergraph such that the edges ...
2
votes
1answer
173 views

Covering a uniform hypergraph with complete $r$-partite hypergraphs

In combinatorial terms, I was wondering how many complete $r$-partite $k$-uniform hypergraphs are needed to cover the edges of the complete $n$-vertex $k$-uniform hypergraph $\binom{[n]}{k}$. An $r$-...
1
vote
0answers
14 views

Is Lexicographic product of two hypergraph is same as their Wreath product??

In page 24 of the paper A survey on hypergraph product by Marc Hellmuth the lexicographic product of two hypergraph is defined as Let $H_1 = (V_1, E_1)$ and $H_2 = (V_2, E_2)$ be two hypergraphs. ...
0
votes
0answers
106 views

Neighborhood structure in a uniform hypergraph

Consider a $k$-uniform connected hypergraph with vertex set $V$ and hyperedge set $E$, as defined in https://en.wikipedia.org/wiki/Hypergraph#Symmetric_hypergraphs . We impose the following condition ...
4
votes
1answer
388 views

Hypergraph $2$-colorability is NP-complete

So far all my searches for a proof of this well-known theorem have led me to the one below (Lovász 1973), reducing $k$-colorability for ordinary graphs to $2$-colorability for hypergraphs. In the ...