0
votes
1answer
14 views

Simple question about indexing edges of an undirected graph.

As far as I understand, for an undirected graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, the set of edges is defined as unordered 2-element subsets of $\mathcal{N}$. So, for example, $\mathcal{E} = ...
1
vote
1answer
25 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
24 views

Is there notation or a name for the complement of the unbounded face of a planar graph?

Let $G$ be a finite graph embedded in $\mathbb{C}$. Let $F$ denote denote its unbounded face. Is there notation or a name for $F^c$ without referring directly to $F$. Of course this is equivalent ...
0
votes
1answer
38 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
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 ...
1
vote
0answers
27 views

Under what conditions is there a common transversal?

Let $S = \{S_1,\dots,S_n\}$ and $T = \{T_1,\dots,T_n\}$ be two collections of finite subsets of $\{1,2,\dots\}$. A transversal for $S$ is a list of elements $s_1,\dots,s_n$, one coming from each ...
0
votes
0answers
31 views

Depth in acyclic graphs

I am struggling to understand a definition in a paper: Given a acyclic (directed!) graph $D=(V,E)$ we define a sequence $Q_i \subset V(D)$ of sets: $$Q_0 = \emptyset,$$ $$ Q_i \textrm{ is ...
0
votes
2answers
66 views

T and F on some discrete math concepts

I was studying and these questions came up on a review guide on the inter webs, but could was wondering if I was correct on them. 1.Let $B$ $\subset$ $A$ and $f$ : $B$ $\subset$ $A$ be a 1-1 and ...
0
votes
0answers
23 views

How to translate these defitions of bipartiteness to each other?

Let $(V,E)$ be a bipartite graph. I'm trying to capture this property and I've come up with two definitions and am surprised/confused that one uses a negation and the other doesn't - still I can't ...
2
votes
0answers
102 views

Hall's marriage theorem explanation

I stumbled upon this page in Wikipedia about Hall's marriage theorem: The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...
1
vote
1answer
62 views

Making minimum number of partitions of a set

Let us consider a set in which every element has an ordered pair of natural number (x,y)( Each pair is distinct) associated with it. Let us define a partition of a set to be consisting of elements ...
1
vote
1answer
601 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 ...
2
votes
1answer
88 views

What is the name of this notation for representing set membership?

What is the name for the membership graph notation used in this question: Kuratowski's definition of ordered pairs ? I'd also appreciate a reference to any explanatory resources. I'd like to ...
0
votes
1answer
31 views

Is this graph transitive?

I have a graph $G = (A,B)$ which is transitive when: $(a,b) ∈ B ∧ (b,c) ∈ B → (a,c) ∈ B$. How can I prove that $G$ is transitive iff it's acyclic?
3
votes
1answer
72 views

Prove that $\dim(X,\succsim)\leq|X^2|$ - A starting point for a journey into order theory

During the last week I kept on thinking about what looked an easy problem at a first glance. Let $(X,\succsim)$ be a preordered set, and define $\mathcal{L}(\succsim)$ as the set of all complete ...
2
votes
1answer
104 views

What does the notation $[V]^2$ mean (in graph theory)?

In graph theory, a graph is a pair $G=(E,V)$ of sets satisfying $E\subseteq[V]^2$. But what is $[V]^2$? I suppose that it is the same as $V\times V=V^2$, but I do not know where the square brackets ...
-4
votes
2answers
1k views

Proving the number of edges in the complete graph Kn

I am trying to find the number of edges in the complete graph: $$K_n=\sum_{i=0}^{n-1} i$$
0
votes
1answer
88 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 ...
2
votes
2answers
283 views

Fuzzy Venn diagram regions labeled in ternary

I have a couple of questions about the Venn diagrams object : Words from the binary alphabet with n letters label each region of an order-n Venn diagram. Is there any more profound connection ...
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
2answers
177 views

Understanding the notation $N/(N_{r}\bigcup N_{v})$ in graph theory

Currently I'm dealing with a graph problem but I don't understand one specific notation. What does the following mean: $$N/(N_{r}\bigcup N_{v})$$ $N$, $N_{r}$, $N_{v}$ are sets of nodes. $N$ is the ...
2
votes
1answer
2k views

How to draw Hasse diagram for divisibilty?

Please help me out.. Is there some appropriate method to draw Hasse diagram My question is $L=\{1,2,3,4,5,6,10,12,15,30,60\}$ Please explain me by step by step solution... Thanks for help..
0
votes
1answer
80 views

Constant $f:[\mathbb{N}]^2\to \{1,2\}$.

Let $[\mathbb{N}]^2$ denote the set collection in size $2$. Now, let $f:[\mathbb{N}]^2\to \{1,2\}$. How can one show that, if we fixing some $n\in \mathbb{N}$, then there exist infinite set ...
4
votes
3answers
96 views

Number of nodes in an infinite binary tree

I know the number of nodes in an infinite binary tree is countably infinite, but I don't understand why. There are $\aleph_0$ levels, and the number of nodes in a binary tree is $2^{\text{number of ...
2
votes
2answers
140 views

Why can disjoint subsets be picked out in these sets?

Still another exercise on Reinhard Diestel Graph Theory, GTM 173, edition 3 (on page 51) Let $A$ be a finite set with subsets $A_1, \cdots, A_n$, and let $d_1, \cdots, d_n \in \mathbb N$. Show ...
-1
votes
1answer
78 views

Confusion about the definition of graphs

From this graph theory lesson : A graph is a non-empty finite set $V$ of elements called vertices together with a possibly empty set $E$ of pairs of vertices called edges. Here are a few ...
8
votes
1answer
859 views

What is the number of bijections between two multisets?

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$. Question: How many bijections are there from $P$ to $Q$? I will define a bijection between $P$ and $Q$ as a multiset $\Phi ...
0
votes
0answers
80 views

System of Distinct Representatives of a collection $\mathbb{A}$ [duplicate]

Possible Duplicate: Difference between pairwise distinct and unique? A just came across the following Definition for an SDR of a collection of sets $ \mathbb{A} $ : Let $ \mathbb{A} = \{ ...
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 ...
2
votes
4answers
711 views

Is the Set of all Graphs Countable?

I am taking an elementary level set theory, and was doing an exercise. The question is "Is the set of all graphs countable?" My intuition tells me it is not but I am not sure how I can use Cantor's ...
0
votes
1answer
508 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
198 views

Cardinality of the set of graphs on a infinite set of vertices

How might one label an infinite graph (which edges can cross over and all nodes are connected to at least 2 edges, such that there are no "dangling lines") to show that there are countably many such ...
2
votes
3answers
210 views

Finding a set of subsets such that for each such subset in the set, there exists another subset in the same set which is non-disjoint

I'm sorry if the title is a bit convoluted. I'm a bit unsure how to formulate this condition in words, see below instead. Say we are given a set $Y$. I want to find the following set: $\mathcal{A}$ ...
2
votes
3answers
172 views

Functions, graphs, and adjacency matrices

One naively thinks of (continuous) functions as of graphs1 (lines drawn in a 2-dimensional coordinate space). One often thinks of (countable) graphs2 (vertices connected by edges) as represented by ...