All Questions
Tagged with graph-theory order-theory
35 questions
28
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
- 35.5k
3
votes
0
answers
127
views
A class of Kripke frames which preserves validity
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...
- 53
10
votes
0
answers
309
views
Mapping graphs to ordinals
Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
- 2,031
1
vote
1
answer
98
views
Characterization of edge posets
Given an acyclic directed graph $G$, the set $E(G)$ of edges of $G$ equipped with the reachable order $\to$ is called the edge poset of $G$, where for two edges $e_1\to e_2$ means that there is a ...
- 153
10
votes
1
answer
492
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
CommunityBot
- 1
11
votes
0
answers
286
views
Does every finite poset have a rigid endomorphism?
Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
- 4,416
5
votes
0
answers
191
views
Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph
This question is very important for my research, which is why I ask it here.
I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
- 63.9k
6
votes
2
answers
882
views
Reconstruction puzzles
[Added: This is a follow-up of an earlier post.]
Consider the following "reconstruction puzzle", stated informally:
Given a concrete poset, e.g. the poset of undirected unlabeled finite graphs ...
CommunityBot
- 1
1
vote
2
answers
245
views
Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube
Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...
- 12.9k
8
votes
1
answer
1k
views
Wikipedia article on forbidden graph substructures
I apologies if this is too trivial a question or if I am over complicating anything here. But I was hoping for some clarification in an article I was reading about forbidden graph substructures on ...
- 2,506
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 14k
6
votes
0
answers
188
views
Generalized graph-minor theorem?
Consider the following generalized graph-minor theorem:
GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...
CommunityBot
- 1
1
vote
0
answers
97
views
Generalization of the linear extension theorem to directed acyclic graphs
Using Zorn's lemma one can prove a generalization of the order extension theorem, that states any acyclic digraph is always contained in another acyclic unilaterally connected digraph on the same ...
- 2,506
0
votes
1
answer
52
views
Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...
- 28.2k
12
votes
1
answer
443
views
Is each cover of the plane by lines minimizable?
A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called
$\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$;
$\bullet$ minimizable if $\...
- 41.9k
4
votes
3
answers
381
views
Is a simple graph the "sum" of a partial order and its dual?
A "$n$-order matrix" $T\in M_n(\mathbb F_2)$ is a matrix such that there exists a partial ordered relation $\leq_T\subset [1,n]^2$ such that :
$T_{ij}=1\Leftrightarrow i\leq_T j$
(where $T_{ij}$ is ...
2
votes
1
answer
104
views
Is a simple graph matrix the sum of a "shiftordered" matrix and its transposed matrix
This is the generalization of a question Is a simple graph the "sum" of a partial order and its dual?
Nik Weaver found a counterexample in a very nice, complete (and instantaneous!) answer,...
- 6,101
3
votes
2
answers
138
views
In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?
Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
- 2,506
4
votes
1
answer
154
views
Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants
In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.
An n-augmented tree is a tree T together with $n$ unary ...
- 3,073
1
vote
0
answers
127
views
Ordinal corresponding to well-quasi-order on graphs
Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order.
In terms of $K$, what is the maximal order ...
- 6,353
4
votes
1
answer
153
views
Posets as graphs with the direct neighbor relation
Given any poset $(P,\leq)$ we define the "direct neighbor graph" as follows. Let $$E_P = \big\{\{a,b\}: (a<b \text{ or } a>b) \text{ and } \; ]\min\{a,b\},\max\{a,b\}[ = \emptyset\big\}.$$
It is ...
- 7,875
0
votes
2
answers
62
views
Largest edge set compatible with graph endomorphisms
Let $V$ be a set and let $V^V$ denote the set of all functions $f:V\to V$. Suppose that $F\subseteq V^V$. Let $[V]^2 = \big\{\{x,y\}: x, y\in V \land x\neq y\big\}$. We say $E\subseteq [V]^2$ is $F$-...
- 2,339
4
votes
0
answers
153
views
Maximality with respect to having no marriage
Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
- 48.9k
17
votes
4
answers
1k
views
Subposets of small Dushnik-Miller dimension
The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, i....
- 31
-1
votes
1
answer
360
views
Modern books about orders and algebras on trees [closed]
Please help to find books about orders and algebras on trees.
If there is no modern books, please advice good old ones!
I'm more interested in finite trees (my current problem), but infinite ones are ...
CommunityBot
- 1
0
votes
0
answers
115
views
Quasi-transitive decomposition of a transitive graph
Let $G=(V,E)$ be a simple digraph that is semi-complete (ie. there's at least one arc between each unordered pair of vertices) and quasi-transitive (ie. its complement is transitive).
Is it true that ...
- 247
3
votes
1
answer
315
views
Directed Hypercube Minimal Cuts
If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,...
CommunityBot
- 1
2
votes
0
answers
116
views
Isomorphic subcategories of directed graphs and presets
For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
- 10.5k
3
votes
1
answer
93
views
Minor ordering for finite graphs
Let $\mathcal{G}_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. ...
- 18.6k
4
votes
2
answers
317
views
Equality-preserving embeddings of finite trees
For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
- 32.1k
3
votes
3
answers
266
views
Name for "lower/upper bounds" of arbitrary relations?
Given a partial order $R_{\leq}$ over a set $D$, the set of upper bounds under $R$ of a subset $S$ of $D$ is commonly defined as $\{ y \in D | \ \forall x\in S, x R y \}$.
(The set of lower bounds of ...
- 747
4
votes
1
answer
503
views
For what classes of comparability graphs are their complements also comparability graphs?
An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...
- 24.7k
1
vote
0
answers
111
views
Set of upper bounds is finite for any finite subset
Is there a term to describe a preordered set $P$ in which any finite subset $S \subset P$ has at most finitely many minimal upper bounds? The preordered sets I'm studying generally aren't join-...
- 11
6
votes
1
answer
392
views
Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?
I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in polynomial-...
- 37.7k
0
votes
0
answers
292
views
Transitive closures and inductive reasoning [solved]
Let's say that r is an endorelation over A (i.e. $r$ is a subset of $A \times A$), $\bar{r}$ is the transitive closure of r (i.e. the least set containing r and being transitive).
Furthermore $r$ has ...
- 165