# Tagged Questions

**-2**

votes

**1**answer

177 views

### Natural constructions (not depending on parameters) [closed]

Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...

**1**

vote

**0**answers

147 views

### Self-modelling structures

Consider - for the sake of simplicity - only graphs as structures.
For undirected graphs $(V, E\subseteq \binom{V}{2})$ let
$E(v)$ be the set of edges $e\in E$ incident with $v$, i.e. $\lbrace e ...

**8**

votes

**1**answer

346 views

### Weakest choice principle required for Robertson-Seymour Graph Minor Theorem?

The main Robertson-Seymour Theorem states that finite graphs form a well-quasi-ordering under the graph minor relation. In other words, in every infinite set of finite graphs, there exist two graphs ...

**7**

votes

**2**answers

403 views

### Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the
Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's
book Subsystems of second order ...

**2**

votes

**1**answer

192 views

### Definability in a language with a single binary predicate

Let the first-order language ${\mathcal{L}}$ have a single binary predicate $P$. Consider the structure whose underlying set is ${\mathbb{Z}}$, the integers, and an ordered pair $(m,n)$ is in $P$ if ...

**10**

votes

**4**answers

1k views

### How are Modal Logic and Graph Theory related?

I am currently taking a graduate logic course on Modal Logic and I can't help notice that there are a certain class of graphs characterized by the modal axioms such as (4) $\Box p \rightarrow \Box ...

**0**

votes

**0**answers

137 views

### The notion of logical difference

Motivating example
All vertices $v$ in a 3-connected graph have degree $d(v) \geq$ 3 (because every two vertices are connected by three independent paths).
What is the "logical difference" between ...

**2**

votes

**1**answer

312 views

### Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...

**2**

votes

**1**answer

457 views

### Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...

**3**

votes

**1**answer

394 views

### Examples of Graphs with Trivial Definable Closure

If I'm giving a lecture on trivial definable closure (as a property of graphs), what is a good example of a graph that I can easily draw to depict the concept of trivial dcl?

**5**

votes

**1**answer

509 views

### Characterization of infinite paths in graphs

First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph. A
pair $(\mathcal{G},s)$ is called a ...

**6**

votes

**4**answers

649 views

### Self-defining structures

The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed.
But consider derived ...

**2**

votes

**3**answers

394 views

### Graph properties: definability and decidability

[This is a side question to Supervenience in mathematics.]
There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not ...

**7**

votes

**3**answers

467 views

### Statistics for Second order properties of Random graphs

Hi!
Let G(N) be the number of graphs with vertices {1, 2, ..., N} and GN(F) be the number of those of them which satisfy graph property F. There is a beautiful result by Glebskii and Fagin that limit ...

**14**

votes

**1**answer

556 views

### Which graphs are elementarily equivalent to their own disjoint sums?

In Stefan Geschke's recent
question,
one of the solutions observed that the graph consisting of
a single infinite beaded chain, a $\mathbb{Z}$-chain where
each integer is connected to its nearest ...

**2**

votes

**1**answer

238 views

### Graph properties and infinite FOL sentences

This question is related to this Question.
Above questions revealed that even though FOL is not expressive enough to describe properties such as Connectivity, Bipartite etc. It is possible to ...

**10**

votes

**3**answers

1k views

### Is non-connectedness of graphs first order axiomatizable?

A recent
question
asked for graph properties that are first order axiomatizable but not finitely axiomatizable.
Connectedness was mentioned in the context. Connectedness can be axiomatized in ...

**2**

votes

**5**answers

719 views

### Monadic Second Order (MSO) logic on graphs

Given a conflict graph $G = (V, E)$, a man has to transport a set $V$ of items/vertices across the river. Two items are connected by an edge in $E$, if they are conflicting and thus cannot be left ...

**7**

votes

**3**answers

308 views

### What are other theories of causality besides graphical models and Bayesian networks?

I am trying to find some data structures/mathemetical theories to represent causal relationships which differ from graphical models or Bayesian Networks. Any ideas?

**23**

votes

**9**answers

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

**6**

votes

**1**answer

655 views

### An ubiquitous pattern of questions

There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):
Can a ...

**38**

votes

**5**answers

4k views

### Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...

**3**

votes

**3**answers

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