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 ...
