0
votes
1answer
27 views

New way of combining information in graphs

So, I am working for a social project involving graph theory. I have a dynamic dataset (weighted and undirected), I made graphs out of them ( for 10 years ). Now, I am trying to find out relations ...
1
vote
1answer
19 views

Name for the type of relation similar to the edge set of a regular directed graph?

For a binary relation over a set, if each member in the set appears the same number of times in the first position and in the second position in the relation, is there a name for such a relation? For ...
1
vote
1answer
23 views

Name for a generalized relation to be a multiset?

A relation between two sets $A$ and $B$ is a subset of $A \times B$. If taking a multiset subset of $A \times B$, e.g. allowing $(a,b)$ appears twice in the subset, is there a name for such a ...
1
vote
1answer
47 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
6
votes
2answers
291 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
0
votes
2answers
29 views

Can I write a Non Homogenerous equation as homogenous

Say I have Fibonacci R.Relation, $$ r^2=r+1 $$ Can I write it as $r^2-r-1=0$? From what I know a homogeneous equation is an equation equated to zero.
2
votes
1answer
133 views

Is there a name for this property of a binary relation? $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. Is there a well-known name for the ...
1
vote
3answers
135 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
0
votes
0answers
28 views

Equivalent of planar graphs for binary relations?

Every graph $G = (V, E)$ defines a binary relation $R$ over the set $V$ where $aRb$ iff $(a, b) \in E$. Similarly, every binary relation $R$ over some set $V$ defines a graph $G = (V, E)$ where $(u, ...
1
vote
1answer
585 views

Transitivity of Relations and Eulerian Cycles

Question: Let $R$ be the relation $\{(1,1),(2,3),(2,2),(3,2),(3,3)\}$ on the set $S=\{1,2,3\}$. Is $R$ an equivalence relation? If $R$ is, describe the partition $\mathscr{P}$ determined by $R$ by ...
0
votes
1answer
64 views

$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
0
votes
1answer
17 views

Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
7
votes
2answers
156 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
0
votes
1answer
85 views

Maximum number of elements, where no two are in relation

I have a set S. I have reflexive, symmetric and non-transitive relation R on SxS. I have to find size of set P, which is the biggest subset of S where : Any two distinct elements of P are not in ...
9
votes
4answers
339 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
1
vote
1answer
2k views

Constructing A Hasse Diagram Using The Covering Relation

I am still having a little difficultly with the covering relation, specifically that when y covers x, $x \prec y$ there is no element in between them, $ x \prec z \prec y$, where x,y, and z are ...
0
votes
1answer
47 views

Equivalence relation $\varsigma$ on ${\mathbb{R}}^2$

How to show that there is exist equivalence relation $\varsigma$ on ${\mathbb{R}}^2$ such that the following conditions hold: Exist only $7$ equivalence classes by $\varsigma$. For every $x,y \in ...
1
vote
2answers
282 views

What's the equivalent of the adjacency relation for a directed graph?

I've found several sources describing a relation notated $\sim$ signifying adjacency in an undirected graph, but nothing explicitly describing an equivalent for a directed graph. I've been using ...
0
votes
1answer
118 views

Construct a graph G for which the is-adjacent-to relation is antisymmetric.

Background: In this a graph is G=(V,E) where V is the set of all vertices and E is a set of 2-element subsets of V. For example: G=({1,2,3,4},{{1,2},{1,3},{2,4}}). E stands for edges similar to a line ...
1
vote
2answers
59 views

Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...
0
votes
1answer
503 views

directed graph representing the inverse relation

Let $R$ be a relation on a set $A$. Explain how to use the directed graph representing $R$ to obtain the directed graph representing the inverse relation $R^{-1}$ ($R$ inverse).
2
votes
1answer
1k views

Transitive and reflexive graph

The answer for this turns out to be only irreflexive. However, how is this not transitive? The definition I have for transitive states "whenever there is a path from x to y then there must be a ...
0
votes
1answer
314 views

Binary relation powers and path length

Let $R\subset A\times A$ a binary relation, and note $a\sim b$ for $(a,b)\in R$. We define $$(a,b)\in R\circ R\Leftrightarrow \exists b\in A : a\sim b, b\sim c$$ and $R^n=R\circ\dots\circ R$. My ...