User hans stricker - MathOverflow

Origins of names of algebraic structures

2010-08-11T22:30:53Z

Consider the names of basic algebraic structures: 'group', 'ring', 'space', 'field', 'Körper', even the name 'structure' itself - all of them time-honoured terms, deeply rooted in our history and culture.

But what has an algebraic field to do with an acre? What has an algebraic group to do with a group of people?

Even when it's known who coined these names (of algebraic structures), it's not obvious why they were choosen and what the connection is between the named structures and what was named originally (or later on). Only those who coined the names could tell.

Are there etymological studies concerning these names - 'group', 'ring', 'space', 'field',... - which elucidate this connection?

Visualizing polyhedra from their 1-skeletons

2013-01-21T10:58:43Z

Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here.

Tools that are able to take an arbitrary polyhedral graph as input and draw the corresponding polyhedron perspectively will most surely rely on an abstract representation of the graph, e.g. by its adjacency matrix. From this abstract representation - presumably - they will also draw the embedded version of the graph (without edges crossing).

I am interested in the underlying algorithms and/or heuristics of

drawing the embedded graph from the adjacency matrix

drawing the polyhedron from the adjacency matrix

drawing the polyhedron from the embedded graph

drawing the embedded graph from the polyhedron

I am asking for references.

Computer programs will most certainly deal with (1) and (2) while humans typically have to solve problems (3) and (4).

I guess that experts have some mental techniques to visualize a polyhedron from looking at its 1-skeleton.

Can these techniques be described, made explicit, and taught?

[Side question: If anyone could give me a visualization of the hexahedral graph 5, I would be thankful.]

Probing a manifold with closed curves

2013-03-14T17:37:00Z

Since fedja's excellent comment on Joseph's question on probing a manifold with geodesics remained uncommented (especially by topologists), I'd like to make a question out of it:

Conjecture: Given an orientable 2-dimensional manifold and two closed curves on it which intersect transversally in exactly one point. Then the two curves cannot be homotopic.

(An immediate consequence of this would be that living on a surface with two such curves, one would know, that it is not homeomorphic to the sphere.)

How to proof this conjecture (if it's true)?

Isometric but differently shaped closed surfaces in $\mathbb{R}^3$

2013-02-28T17:25:31Z

Starting from the following inclusions for surfaces $M_1,M_2$ in $\mathbb{R}^3$:

$M_1,M_2$ have the same shape, i.e. are related by an ambient isometry

→ $M_1,M_2$ have the same metric

→ $M_1,M_2$ have the same Gaussian curvature

the only examples of isometric but differently shaped surfaces in $\mathbb{R}^3$ I have seen so far do have boundaries:

cone and cylinder
catenoid and helicoid
other associate families of isometric minimal surfaces.

I wonder if there are no (examples of) isometric but differently shaped closed surfaces, and why that could be. (I am particularly interested in smooth surfaces.)

And I am still looking for (closed) surfaces with the same Gaussian curvature but different metrics.

A picture gallery would be highly welcome, because I really would like to see two such (non-)isometric surfaces.

Some questions about ideal knots

2013-02-27T23:49:37Z

The ropelength of a knot curve $C$ is defined as the ratio $L(C) = \lambda(C)/ \tau(C)$, where $\lambda(C)$ is the length of $C$ and $\tau(C)$ is the thickness of the knot defined by $C$ [from Wikipedia]. Intuitively the thickness is the maximally possible thickness that $C$ as a rope can have (without intersecting itself).

The infimum ropelength of the realizations of a knot type is a knot invariant. A knot that minimizes ropelength is called an ideal knot.

Question 1: How can it be proved that there are ideal knots at all (besides the plane circle which is the ideal unknot)?

Another question concerns the number (of shapes) of ideal knots of a given knot type.

Question 2: Is the number of ideal knots known, at least for some knot typyes? Can it be calculated from other knot invariants, eventually?

(Assuming that this number is finite, it would be another knot invariant – the more interesting the more it can vary.)

Question 3: Are there ideal knots of constant curvature (besides the plane circle)?

Alternatively: Are there approximations of ideal knots that approximate constant curvature?

(The last one is a refinement of another question.)

Rado graph containing infinitely many isomorphic subgraphs

2010-03-17T10:26:41Z

The Rado graph contains every finite graph as an induced subgraph. It surely contains some finite graphs infinitely often as an induced subgraph, e.g. $K_2$. Does it contain all finite graphs infinitely often as an induced subgraph? Or can an example of a graph be given that is not contained infinitely often?

Possible curvatures of the topological sphere

2013-02-24T22:13:22Z

Consider the family $\mathbb{S}$ of compact oriented surfaces homeomorphic to the 2-sphere $\mathcal{S} = S^2$. Consider arbitrary continuous mappings $k: \mathcal{S} \rightarrow \mathbb{R}$ which obey the condition $\int_\mathcal{S} k = 4\pi$. The latter looks like the Gauss-Bonnet condition for 2-spheres, and that's why I want to call those mappings “curvature-like”.

For which curvature-like mappings $k$ does exist a surface $S \in \mathbb{S}$ which $k$ is the Gaussian curvature of?

In other words: For which curvature-like mappings $k$ does exist a surface $S \in \mathbb{S}$ with a homeomorphism $s: S \rightarrow \mathcal{S} $ such that $k \circ s$ equals the Gaussian curvature $\kappa: S \rightarrow \mathbb{R}$?

Background (and for comparison's sake): When one considers (plane) Jordan curves - which are homeomorphic to the 1-sphere $S^1$ - and continuous “curvature-like” mappings $k: S^1 \rightarrow \mathbb{R}$ which obey the condition $\int_{S^1} k = 2\pi$ – in accordance to Hopf's Umlaufsatz – then the additional condition for a curvature-like mapping to be a “real” curvature seems to be given by the four-vertex theorem.

Possible curvatures of the topological torus

2013-02-25T08:07:06Z

Consider the family $\mathbb{T}$ of compact oriented surfaces homeomorphic to the torus $\mathcal{T} = S^1 \times S^1$. Consider arbitrary continuous mappings $k: \mathcal{T} \rightarrow \mathbb{R}$ which obey the condition $\int_\mathcal{T} k = 0$.

For which curvature-like mappings $k$ does exist a surface $T \in \mathbb{T}$ which $k$ is the Gaussian curvature of?

For the topological sphere the answer seems to be: for all. Can the proof of the latter - which I do not know - be generalized for arbitrary compact oriented surfaces? Or is it already a general proof for arbitrary surfaces?

Geodesics in polyhedral graphs

2013-02-05T00:46:38Z

Let $e = \lbrace u,v\rbrace$, $e' = \lbrace v,u'\rbrace$ be edges of an undirected graph $G$ and $ee'$ be the path from $u$ through $v$ to $u'$. The following defintions make sense for every graph and thus are purely combinatorial:

Definition 1: $ee'$ is a pre-geodesic when it is the unique shortest path between $u$ and $u'$

Definition 2: A pre-geodesic $ee'$ is a geodesic when there is no other edge $f$ through $v$ such that $ef$ or $e'f$ is a pre-geodesic.

The first condition is motivated by the fact that geodesics in differential geometry are locally shortest paths and as such locally unique. It prevents the graph

from having geodesics.

The second condition reflects the fact, that geodesics usually do not “split”. It prevents the graph

from having geodesics.

But now, let's restrict to polyhedral graphs. I wonder if it's true for polyhedral graphs that only a small number of patterns of geodesics going through a given vertex $v$ are possible:

Which patterns?

How to prove this?

Have a look at this gallery of vertices $v$ (grey, drawn with all their neighbours) with degree at most 6 and at most three geodesics (red, blue, green) passing through them (all the other vertices may or must have further neighbours):

Is this gallery essentially complete?

If so: how to prove it?

Otherwise:

Is there a polyhedral graph with a vertex of degree 7 with a geodesic passing through it?

Is there a polyhedral graph with a vertex with four geodesics passing through it?

Ways to look at a polyhedral graph

2013-02-02T15:48:04Z

Motivation

There are at least three interpretations of an abstract polyhedral (= planar 3-vertex-connected) graph:

the 1-skeleton of a convex polyhedron (when embedded into $\mathbb{R}^3$)
a polygonization of the sphere (when embedded into the sphere $\mathbb{S}^2$)
a polygonization of a polygon – for each of its faces (when embedded into the plane $\mathbb{R}^2$)

In any case there are many geometric realizations:

of a polyhedron
of a polygonization of the sphere
of a polygon and its polygonizations

Question

I'd like to understand in an abstract setting:

What do these interpretations and realizations have to do with each other?

Example

For many (but not all) polyhedral graphs there is a realization as a convex polyhedron that is inscribable into the sphere. A central projection of this polyhedron back onto the sphere induces a polygonization of the sphere.

Taken for granted is Steinitz' theorem. The question is not about this.

EDIT: For completeness' sake I should mention embeddings of a polyhedral graph into:

the hyperbolic space $\mathbb{H}^2$
the 3-dimensional sphere $\mathbb{S}^3$
the hyperbolic space $\mathbb{H}^3$

Degree of freedom restricted by inequalities

2013-01-22T23:01:20Z

Motivational example

Consider a polyhedral graph $G$. A realization of $G$ is given by a convex polyhedron which is - essentially - characterized by the angles between the edges emanating from each vertex. There are $\sum_v d(v) = 2E$ such angles, so the degree of freedom $\mathsf{d}$ of a polyhedron is $\mathsf{d}\leq 2E$ (with $E$ the number of edges). But the angles cannot be choosen freely: for every (flat) face of the polyhedron the interior angle sum must obey a (strict) equality. Thus, $\mathsf{d}\leq 2E - F$ (with $F$ the number of faces). Because the polyhedron is supposed to be convex there is another restriction: for every vertex $v$ of the polyhedron the sum of angles between the edges emanating from $v$ has to be less than $2\pi$. Thus, we have $V$ additional restricting inequalities (with $V$ the number of vertices). But because inequalities are somehow "weaker" than equalities we cannot simply deduce that

$$\mathsf{d}\leq 2E - F - V = E - \chi = E - 2$$

(with $\chi$ the Euler characteristic of the graph/polyhedron). But by which amount $\mathsf{d}$ might be greater than $E-2$?

Question

The original question is (more abstractly) concerned with the question how inequalities enter into the calculation of a "degree of freedom":

How can an (eventually non-integer) degree of freedom be defined when inequalities are involved?

The notion of logical difference

2013-01-22T00:08:24Z

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 (i) 3-connectedness and (ii) minimal degree $\delta(G) = 3$? That is: which properties $\phi(G)$ make the statement

The graph $G$ is 3-connected if and only if $\delta(G) = 3$ and $\phi(G)$

true?

Question

Consider a setting with a fixed language and theory. Let two properties $F(x)$ and $G(x)$ with $(\forall x) F(x) \rightarrow G(x)$ be given. Ask the question: Are there properties $H(x)$ such that $(\forall x) F(x) \leftrightarrow G(x) \wedge H(x)$? And which?

For which languages and theories and/or in which cases might such a question have a definite and sensible answer? By which means could the answer be derived?

It's - very loosely speaking - about resolving some kind of "logical equation":

$F > G \Rightarrow (\exists H)\ F = G + H \Rightarrow \bf{H = F-G}$.

Unique circular ordering of edges around a vertex

2013-01-16T09:50:48Z

Consider the property of a vertex $v$ of a planar graph $G$ that the circular ordering of its edges is the same (upto orientation) for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$.

Does this property have an official name?

(How) can it be defined purely combinatorially?

(How) can planar graphs be characterized in which every vertex has this property?

Answer by Hans Stricker for Unique circular ordering of edges around a vertex

2013-01-16T17:07:12Z

It might be simpler than I believed:

ad 2. The circular ordering of the edges (= neighbours) of a vertex $v$ of a planar graph $G$ is unique (upto orientation) when the neighbours of $v$ lie on a cycle that does not contain $v$.

If they happen to lie on more than one cycle their circular ordering doesn't depend on which.

Jordan-like cycles in graphs

2013-01-14T14:11:28Z

[Added another complementary question below.]

Motivation

The 1-skeleton of the triangular bipyramid seems to be the smallest connected planar graph $G$ with the following

Property: There is a cycle $\gamma$ ($\color{red}{\mathsf{red}}$) in $G$ with exactly two connected components $G_1, G_2$ of $G - \gamma$ such that for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$ the component $G_1$ ($\color{blue}{\mathsf{blue}}$) is contained in the interior of $\pi(\gamma)$ and the other component $G_2$ ($\color{black}{\mathsf{black}}$) is contained in the exterior of $\pi(\gamma)$ – or vice versa.

Definition: A cycle $\gamma$ in the graph $G$ is a Jordan cycle if $G - \gamma$ splits up into exactly two connected components $G_1, G_2$ such that for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$ the component $G_1$ is contained in the interior of $\pi(\gamma)$ and the other component $G_2$ is contained in the exterior of $\pi(\gamma)$ – or vice versa.

Questions

(How) can the property of being a Jordan cycle $\gamma$ be defined purely combinatorial, without mentioning graph embeddings $\pi$ and Jordan curves $\pi(\gamma)$?

(How) can planar graphs containing a Jordan cycle be characterized purely combinatorially?

ADDED: Can planar graphs be characterized in which every cycle is a Jordan cycle?

Can you determine whether a graph is the 1-skeleton of a polytope?

2009-12-18T09:57:57Z

How do I test whether a given undirected graph is the 1-skeleton of a polytope?

How can I tell the dimension of a given 1-skeleton?

Almost or probably complete graph invariants?

2010-04-22T14:06:55Z

Assuming that there are no known complete graph invariants in the spirit of Harrsion's question that do not depend on any labelling (see graph property at Wikipedia), I wonder if there are graph invariants that are

almost complete, i.e. discriminating almost all finite graphs up to isomorphism
almost complete in a weaker sense, i.e. discriminating all finite graphs except for a small, but finite fraction (the smaller the fraction the greater the invariant's discriminating power)
probably complete, i.e. not proven to be incomplete yet (e.g. by counterexamples)

Can anyone provide examples or references?

Reconstruction conjecture: Can other decks do the job?

2010-05-19T09:06:23Z

The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.

Question: Have other decks been investigated, finding out that only vertex-deleted subgraphs can do the job? If so: Which property of vertex-deleted subgraphs makes them exceptional?

I have three candidates in mind, others are conceivable. (For the sake of simplicity I consider only simple connected graphs $G$.)

the deck of sub-maximal neighbourhoods: Let the sub-maximal neighbourhood of $v$ be the $v$-rooted graph constructed from $G$ by deleting all vertices with maximal distance from $v$.
the deck of distinguishing neighbourhoods: Let the distinguishing neighbourhood of $v$ be the smallest $n$-neighbourhood of $v$ which distinguishes it from all vertices not conjugate to it ($n$-neighbourhood = the $v$-rooted induced subgraph containing all vertices $w$ with distance $d(v,w) \leq n$).
the deck of crossref-deleted subgraphs: Let the crossref-deleted subgraph with respect to $v$ be the $v$-rooted graph constructed from $G$ by deleting all edges between vertices that have the same distance from $v$.

Note that the vertex-deleted subgraph with respect to $v$ is nothing but the $v$-rooted graph constructed from $G$ by deleting all edges between $v$ and its neighbours.

I am not good in systematically constructing counterexamples, and I do not have very much intuition about general graphs. So, any counterexample to one of the candidates above would be very welcome.

What I do know is that a) trees are trivially reconstructible from their deck of crossref-deleted subgraphs, that b) graphs with one node of which the distinguishing neighbourhood is the whole graph are trivially reconstructible from their deck of distinguishing neighbourhoods, and that c) reconstructing (very) small graphs from one of the decks above is fun.

Approximating Jordan curves

2013-01-05T23:50:30Z

I'd like to capture the intuitive notion that a Jordan curve $\gamma_2$ “follows” or “approximates” another Jordan curve $\gamma_1$, i.e. goes somehow “parallel” to it or “oscillates” around it.

Consider a differentiable Jordan curve $\gamma_1: [0,1] \rightarrow \mathbb{R}^2$ and its normals, seen as straight lines crossing the curve perpendicularly. Consider another Jordan curve $\gamma_2$ with the following properties:

Each normal of $\gamma_1$ crosses $\gamma_2$ at least once. I.e., for each normal $n(s_1)$ of $\gamma_1$ there is an $s_2$ such that the point $\gamma_2(s_2)$ lies on $n(s_1)$.
Furthermore when $s_1 < s_1'$ then there are unique $s_2 \le s_2'$ such that $\gamma_2(s_2)$ lies on $n(s_1)$ and $\gamma_2(s_2')$ lies on $n(s_1')$.

Do these conditions suffice to capture the notion described above? For which “pathological ” cases do they eventually fail? How then would they have to be adjusted to capture the notion?

Further questions:

Under which extra conditions does “$\gamma_2$ follows $\gamma_1$” imply that $\gamma_1$ follows $\gamma_2$?
When $\gamma_2$ follows $\gamma_1$, (how) can the area enclosed by $\gamma_1$ and $\gamma_2$ be calculated via the distance function $d(s_1) = |\gamma_1(s_1) - \gamma_2(s_2)|$
($s_2$ the unique parameter according to condition 2 above)?

(Let the area enclosed by $\gamma_1$ and $\gamma_2$ be the symmetric difference $X_1 \triangle X_2 = (X_1 \cup X_2) \setminus (X_1 \cap X_2)$ of the areas $X_1, X_2$ enclosed by $\gamma_1$ and $\gamma_2$.)

Generalization of the isoperimetric inequality

2012-12-30T17:48:02Z

Preliminaries

Suppose that $\Gamma$ is a simple (sufficiently smooth) closed curve in $\mathbb{R}^2$ with length $L$ and enclosing an area $A$. Suppose furthermore that $\gamma:[0,L]\rightarrow\mathbb{R}^2$ is a parametrization-by-arclength for $\Gamma$ so that $|\gamma '(s)|=1$ for every s, i.e.

$$L = \int_0^{L} |\gamma'(s)| $$

The total (absolute) curvature can be defined by

$$C = \int_0^{L} |\gamma''(s)| = \int_0^{L} \kappa(s)$$

It can be shown that $C\ge 2\pi$. Equality holds iff $\Gamma$ is convex.

The isoperimetry inequality

$$4\pi A\le L^2$$

(equality holds iff $\Gamma$ is a circle) can be stated using another derivative of $\gamma$

$$\Omega = \int_0^{L} ||\gamma''(s)|'| = \int_0^{L} |\kappa'(s)|$$

A closed curve $\Gamma$ is a circle $\mathsf{O}$ iff $\Omega = 0$. (Edit: Pietro correctly pointed out that the initial formula $\int_0^{L} |\gamma'''(s)|$ would not make sense.) This implies

$$\left(( L_{\Gamma} = L_{\mathsf{O}}) \wedge (C_{\Gamma} = C_{\mathsf{O}}) \wedge (\Omega_{\Gamma} \ge \Omega_{\mathsf{O}})\right) \rightarrow (A_{\Gamma} \le A_{\mathsf{O}})$$

for all closed curves $\Gamma$ and circles $\mathsf{O}$.

Question

I wonder if and how it could be shown that a generalization of the last proposition holds:

$$ \left((L_{\Gamma} = L_{\Gamma'}) \wedge (C_{\Gamma} = C_{\Gamma'}) \wedge (\Omega_{\Gamma} \ge \Omega_{\Gamma'})\right) \rightarrow (A_{\Gamma} \le A_{\Gamma'}) $$

for all closed curves $\Gamma, \Gamma'$, i.e. of two curves of the same length and the same absolute curvature the one with greater change rate of curvature has the smaller area.

How would this – probably using Fourier analysis – be shown for ellipses with the same perimeter?

Combinatorial geodesics

2012-12-09T12:50:14Z

[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]

I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics – all from differential geometry – can be understood in abstract graphs, i.e. what their combinatorial counterparts might be.

Specifically, I'd like to know whether the following relation among adjacent edges in a simple graph has been explored, under which name, and in which context:

Definition: Two adjacent edges e, e' have the same direction iff

the path ee' is the unique shortest path between its endpoints

neither e nor e' is part of another unique shortest 2-edge-path through their common vertex

The first condition is motivated by the fact that geodesics in differential geometry are locally shortest paths and as such locally unique. It prevents the graph

from having edges with the same direction.

The second condition reflects the fact, that geodesics usually do not “split”. It prevents the graph

from having edges with the same direction.

Definition: Paths of length at least 2 in which adjacent edges have the same direction are called combinatorial geodesics.

Note, that even a single pair of edges having the same direction is a (minimal) combinatorial geodesic. But no single edge is a combinatorial geodesic.

It's an easy excercise to find combinatorial geodesics in some planar graphs and/or 3-vertex-connected graphs (seen as polygonizations/tilings of surfaces).

In trees (with minimal non-leaf degree 3) there are no geodesics at all.
In finite, infinite, and “torified” triangular and rectangular grid graphs there are geodesics.
In infinite and in “torified” hexagonal grid graphs there are no geodesics.
In polyhedral graphs there are – in general – no geodesics.

Things get really interesting, I believe, when one considers e.g. non-regular tilings of the plane – from “slightly non-regular” (= “regular with a few perturbations”) to “completely random”. One can investigate the “geodesic structure” of such graphs: which geodesics are there, and how are they interconnected? [geodesic structure ⇄ cycle structure]

[The notion of “true shortest paths” between two vertices with several non-unique shortest paths between them – like in the rectangular grid – shall be subject of a follow-up question. It can be easily defined based on combinatorial geodesics.]

To repeat my questions from above:

Have this relation of “having the same direction” and this concept of “combinatorial geodesics” been explored, under which name, and in which context?

Abstract characterization of polygonizations

2012-11-29T18:44:42Z

Consider a polygonization of the plane by convex polygons of a given minimal size that meet edge-to-edge and vertex-to-vertex.

^{What's the “official” name of such a polygonization?}

Such polygonizations of the plane induce infinite graphs.

How can such abstract graphs be characterized?

Somehow like this: “A graph is induced by a polygonization of the plane iff it is infinite, planar, 3-vertex-connected, and P.” (The question asks for property P, since infinite, planar and 3-vertex-connected those graphs obviously are.)

Is it true, that the graphs that are induced by a polygonization of the sphere are exactly the polyhedral graphs which in turn are exactly the finite planar 3-vertex-connected graphs?

Finally I want to know:

Can the graphs be characterized that are induced by a polygonization of any surface?

^{For the record: I asked this question at MSE before but it didn't earn a lot of interest.}

Sets = structured sets without structure

2012-11-22T00:18:51Z

Motivation

There is presumably no single and widely accepted formal definition of structured sets = sets plus structure based on sets as primitive objects, but several approaches are around. See e.g. structures (model theory), echelons (Bourbaki), frames (Moschovakis). I don't want to discuss these approaches, but for simplicity's and specifity's sake I want to pick out one especially simple definition of rather generic structured sets — graphs (which among other things are able to interpret any structured set).

When we start with the „graph“ of sets $U = \langle V,\in\rangle$, sets as primitive objects are „defined“ just by

$$\text{Set}(X) :\equiv X\ \epsilon\ V$$

with $\epsilon$ indicating class membership. Graphs (structured sets), then, are - rather sophisticatedly - defined by

$$\text{Graph}(X) :\equiv (\exists S,R\ \epsilon\ V)\ R \subseteq S^2 \wedge X = \langle S,R\rangle$$

To complete the picture we define

$$\text{Relation}(X) :\equiv (\exists S\ \epsilon\ V)\ X \subseteq S^2$$

Thus, a graph is a set plus a relation over it, usually written as $G = \langle V,E\rangle$.

Interlude

Oppose this set-based picture to the category $\mathsf{Graph} = \langle \mathcal{O},\mathcal{M},\dots\rangle$ with $\mathcal{O}$ the class of all graphs as primitive objects, related by graph homomorphisms $\mathcal{M}$, etc. Thus graphs as primitive objects are defined by

$$\text{Graph}(X) :\equiv X\ \epsilon\ \mathcal{O}$$

To define „set“ as a now derived concept one might try to resolve the above „equation“ informally to obtain sets = structured sets minus structure. Thus, sets don't have any structure (anymore), so morphisms as structure-preserving functions don't have to preserve any structure (anymore), so every function from a set to any other graph (= structured set) is a morphism in $\mathcal{M}$. According to the standard definition of graph homomorphism, the graphs being sets are exactly the edgeless graphs (which complies with intuition).

Translating this into categorical terms we obtain:

$$\text{Set}(X) :\equiv (\forall\ Y\ \epsilon\ \mathcal{O})(\exists\ f\ \epsilon\ \mathcal{M})\ f: X \rightarrow Y$$

Making use of categorical terminology we can equivalently say: Let $\mathcal{C}/$ be the quotient category of $\mathcal{C}$ which identifies all morphisms (if present) from $A$ to $B$ as one. Then:

$$\text{Set}(X) :\equiv X\ \text{is an initial object in } \mathsf{Graph}/$$

Question(s)

I am aware that I didn't even mention the category $\mathsf{Set}$ of sets and the notion of a concrete category (even though $\mathsf{Graph}$ is a concrete category).

What I'd like to learn is - among other things - how the above definition of being a set relates to the usual notions:

Which concrete categories don't have sets?
Which non-concretizable categories do have sets?

A weaker concept of graph homomorphism

2012-11-11T22:38:51Z

In the category $\mathsf{Graph}$ of simple graphs with graph homomorphisms we'll find the following situation (the big circles indicating objects, labelled by the graphs they enclose, arrows indicating the existence of a homomorphism):

Speaking informally, the "obvious" structural relatedness between the two circle graphs $C_3$ and $C_4$ reduces to its two common subgraphs $P_3$ and $P_4$, with $P_3$ being a subgraph of $P_4$.

But even though there is an "undeniable" structural relatedness between $C_3$ and $C_4$, there is no single graph homomorphism between the two. This in complete contrast to the category $\mathsf{Top}$, where they are even isomorphic. (Instead of this: no arrows between $P_i$ and $C_j$!)

But why is there no graph homomorphism between $C_3$ and $C_4$? There are two interrelated reasons:

If all vertices of a graph were forced to have a self-loop, there would be a homomorphism from $C_4$ to $C_3$, since two adjacent vertices $x,y$ were allowed to be mapped onto the same vertex $f(x)=f(y)$. Furthermore, there would also be a homomorphism from $P_4$ to $P_3$.
If one insists on graphs to be loop-less (as in topological graph theory?), one might instead weaken the definition of a graph homomorphism. Instead of defining $f:G\rightarrow G'$ to be a homomorphism when $(x,y) \in E(G)$ implies $(f(x),f(y)) \in E(G')$, one might define it like this:

$f:G\rightarrow G'$ is a (weak) homomorphism when $(x,y) \in E(G)$ implies $f(x) = f(y) \vee (f(x),f(y)) \in E(G')$.

My questions are:

In which contexts does this definition of a (weak) homomorphism between simple graphs have drawbacks other than not being standard, e.g. technical ones?
Is there a known or imaginable "problem" that might be easier to handle with weak homomorphisms (other than the missing homomorphism between $C_4$ and $C_3$ which isn't really a problem)?
Might weak homomorphisms be conceptually more appropriate, i.e. catch the "meaning" of structure preserving better?
Where can I find weak homomorphisms in the literature, maybe under another name?

Geodesics on a twisted torus

2012-10-23T22:18:55Z

^{This is a repost of a question I posted at MSE.}

Mark L. Irons' paper The Curvature and Geodesics of the Torus gives a concise overview of the geodesics on the torus:

There are five clear-cut families of geodesics.
Most of the geodesics are "ergodic": aperiodic and covering either the entire surface - by spiraling endlessly around - or substantial parts of it.
Some of the geodesics are "boring": the meridians, the inner and the outer equator
A few of them are "æsthetically pleasing": returning to their starting point after just a few circuits.

Does the structure of geodesics change when twisting the "hose" before gluing its ends?

E.g., there might be no equators anymore because after twisting the (two) equators lost their "ends".

Spectral graph theory: Interpretability of eigenvalues and -vectors

2010-05-17T08:09:00Z

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally distributed on the unit cycle: the $n$-th roots of unity (from complex analysis) come up in a completely discrete context! What's more: The coordinates of the eigenvector can be "interpreted" straight forwardly when assigned properly to the vertices.

There's another straight-forward interpretation of an adjacency eigenvector: the eigenvector corresponding to the largest eigenvalue gives the relative importances of the vertices, being proportional to the sum of the relative importances of its neighbors.

Question: Can more - or eventually all - adjacency eigenvectors be sensibly "interpreted"?

Or does it in general depend on the type of graph, whether and how the eigenvectors can be interpreted, and the first example above is just a curio?

What about the interpretation of the eigen-values? Do at least some of them "mean" something conceivable?

The ABC of categories: ABstract vs Concrete

2012-10-12T22:37:48Z

From Wikipedia:

A concrete category is a category that is equipped with a faithful functor to the category of sets.

This functor makes it possible to think of the objects of the category as sets with additional structure, and of its morphisms as structure-preserving functions.

This definition gives rise to the well-established dichotomy between concrete and abstract categories.

The examples of abstract (= non-concrete) categories I've heard of come in two flavours:

categories with structured sets as objects, and some other sort of structure-preserving maps than standard homomorphisms, e.g. interpretations. (I understand that - basically - interpretations are structure-preserving maps, just involving re-definitions of individuals (as n-tupels) and relations.)
categories with structured set as objects, and equivalence classes of structure-preserving maps as morphisms, e.g. the homotopy category of topological spaces or much simpler: the category $C'$ which collapses all arrows $X \rightarrow Y$ of a (concrete) category $C$ into one (what's its name?)

[Side remark: The trivial equivalence relation on morphisms: $f \sim g :\equiv f = g$ leaves a given category $C$ unchanged.]

Given such a vast variety of possible definitions of structure-preserving maps and equivalence relations between them, I wonder why only classical homomorphisms and the trivial equivalence relation give rise to so-called concrete categories?

The other way around:

What is an example of an abstract category (in the standard sense) with structured sets as objects, such that we cannot think of its morphisms as some equivalence class of some sort of structure-preserving maps?

Answer by Hans Stricker for Complete graph invariants?

2012-09-19T10:56:58Z

The sequence of homomorphism numbers $|Hom(F_i,G)|$ for all (isomorphism types of) graphs $F_i$ is an invariant of $G$ (see Lovász, Operations with structures).

(Does this fit your bill? Or do you want finite invariants only?)

Is homotopy definable by categorical means?

2012-09-15T16:00:17Z

Is being homotopic - as a relation between two continuous functions, i.e. morphisms in Top - definable by categorical means? Can one detect from the context of dots and arrows, whether two parallel arrows in Top are homotopic to each other? Or from another ("higher") categorical point of view?

(If this were the case the relationship between Top and its quotient category hTop was purely categorical and not grounded on extra-categorical properties.)

Theory mainly concerned with $\lambda$-calculus?

2010-01-15T11:08:24Z

Automata theory is mainly concerned with Turing machines and all its relatives-in-spirit. $\lambda$-calculus is rather rarely mentioned in textbooks on automata theory.

What's the common name of the theory mainly concerned with $\lambda$-calculus and its relatives? (I think, "mathematical logic", "computability theory", "programming language theory" and "recursion theory" are too general, compared to "automata theory". But there should be an "$\lambda$-theory", shouldn't it?)

Comment by Hans Stricker

2013-03-16T18:25:59Z

@Ryan: Thanks again for the hint to Guillemin & Pollack. I received the book today - and it's love of first sight.

Comment by Hans Stricker

2013-03-15T17:53:02Z

Why has this question been closed? How can it be "no longer relevant"? (I mean: the longer people contribute examples, the better.) (BTW: I do have an astonishing example.)

Comment by Hans Stricker

2013-03-14T20:21:29Z

@Mariano & Ryan: Sorry for the dumb question - of course I should have tried googling. (I have unwantedly switched into "chat mode".)

Comment by Hans Stricker

2013-03-14T19:16:42Z

What does "injectivity radius" mean? Why not just "radius"?

Comment by Hans Stricker

2013-03-14T19:07:30Z

@Mariano: I grinned over your "few seconds" - for others it takes a few years!

Comment by Hans Stricker

2013-03-14T19:05:25Z

I only begin to learn that and why orientability is crucial for my question. So excuse me for not having mentioned orientability in my original question.)

Comment by Hans Stricker

2013-03-14T18:58:25Z

Another side question: Do "tubular neighbourhoods" in your understanding have to do with the thickness/ropelength of knots?

Comment by Hans Stricker

2013-03-14T18:46:53Z

@Ryan: Great! (Didn't expect to get such a concise answer.)

Comment by Hans Stricker

2013-03-14T18:13:07Z

@Ryan: Can you tell - by the way - how to aquire a power of imagination like yours (which I envy you for). How can one come to see at once that "the central circle of a Moebius band self-intersects once with many transverse perturbations of itself"? (I assume this is something you see, but for ordinary people like me it requires a very lot of thinking about it.) The same question - by the way - goes to Mariano's first comment to my original question. So you don't have to take it too serious.

Comment by Hans Stricker

2013-03-14T17:54:14Z

Sorry, I just added "orientable" (thanks to maproom's hint). Is your additional assumption equivalent to require the manifold to be orientable?

Comment by Hans Stricker

2013-03-14T17:51:34Z

@maproom: Indeed, I had only orientable surface in mind. So I added it. Thanks for the correction!

Comment by Hans Stricker

2013-03-12T09:34:37Z

@fedja: Is it, that one just has to show that two such loops - with just one intersection which is not a "kissing" - cannot be homotopic? Such that the fundamental group is not trivial?

Comment by Hans Stricker

2013-03-10T16:34:41Z

Is there someting new concerning fedja's interesting comment, in the meanwhile?

Comment by Hans Stricker

2013-03-04T23:23:46Z

It's not only nice: it's great!

Comment by Hans Stricker

2013-03-04T09:46:05Z

Robert Connelly's flexible polyhedron at IHES: youtube.com/…