User gejza jenča - MathOverflow

Answer by Gejza Jenča for Does this property of a partially ordered set have a name?

2013-05-17T18:48:59Z

In the world of partially ordered abelian groups, this is the interpolation property. These groups are called partially ordered abelian groups with interpolation, or simply interpolation groups. Intuitively, I think about them as "almost as nice as lattice ordered abelian groups".

A simple example of a non-lattice ordered interpolation group is the set of all polynomial functions $\mathbb R\to\mathbb R$.

Probably the most important subclass is the class of dimension groups. As proved by Effros, Handelman and Shen in 1980, dimension groups classify the approximate finite dimensional $C^*$-algebras (via the $K_0$ functor).

I recommend this book by Goodearl -- very readable, he is an excellent writer.

Is there any nontrivial monad on the category of graphs?

2013-04-18T11:49:47Z

The question is in the title, but let me specify what I mean by the category of graphs.

In the context of this question, the category of graphs is the category of symmetric irreflexive relations. That means, not the category of symmetric reflexive relations. That means, no loops and at most one edge between vertices.

Answer by Gejza Jenča for Discovering and selecting conferences

2013-01-29T20:07:53Z

Conferences in General Algebra and Related Fields, maintained by Keith Kearnes.

Links to Combinatorial Conferences, maintained by Douglas B. West.

Combinatorics and related conferences, maintained by Peter Cameron.

Answer by Gejza Jenča for Generating function of a regular language

2013-01-19T00:22:10Z

This is basically equivalent for finding an unambiguous regular expression for the language. This MO answer explains how to do it, given an DFA $\mathcal A$.

The rest is easy:

replace $\emptyset$ by $0$
replace $\epsilon$ by $1$
replace any symbol with $x$
replace concatenation with multiplication
replace $\cup$ with $+$
replace Kleene star with $1/1-f(x)$.

Source: this paper.

Answer by Gejza Jenča for Tools for collaborative paper-writing

2012-09-25T16:28:31Z

Gist is very useful for initial writeup of ideas. Allows to create a git repository for a small file instantly. Anyone can edit the file and save (commit) a new version. Does not allow branching -- only the newest version is editable. Registration is not necessary, but useful.

Feel free to edit this gist.

Answer by Gejza Jenča for Fundamental problems whose solution seems completely out of reach

2012-07-02T16:10:28Z

Is every finite lattice a congruence lattice of a finite (universal) algebra?

Astonishingly, by Pálfy and Pudlák, this question is equivalent to a question in group theory: is every finite lattice isomorphic to an interval of the subgroup lattice of a finite group?

The category of posets

2012-03-16T15:53:21Z

I am trying to teach myself category theory and, as a begginer, I am looking for examples that I have a hands-on experience with.

Almost every introductory text in category theory contains following facts.

The class of all posets with isotone maps is a category (called $Pos$).
Every individual poset $P$ is a category, with comparable pairs $x\leq y$ as arrows. This can be called "a categorified poset".

Sometimes, product and coproduct in $Pos$ is characterized and (less frequently) it is pointed out that a Galois connection can be characterized as a pair of adjoint functors of categorified posets. Also, it is sometimes mentioned that products and coproducts in categorified posets are joins $\vee$ and meets $\wedge$, so a categorified poset has products and coproducts iff it is a latttice.

Moreover, some texts contain the fact that the category of finite posets and the category of finite distributive lattices are dually equivalent -- this is extremely useful.

But I cannot find much more. For example, when I tried to search for equalizers and coequalizers in $Pos$, the only source I found is the PhD thesis by Pietro Codara, available here, which is from 2004 and characterizes (co)equalizers in $Pos$.

Does anyone know about some other sources of information about $Pos$ from the category-theoretic viewpoint? Specifically, I am looking for things like

useful functors to $Pos$ and from $Pos$,
pullbacks, pushouts and other universal constructions in $Pos$,
examples of adjoint functors, applications of Yoneda lemma etc.

What is this subclass of $k$-colorable graphs called?

2011-10-14T16:51:54Z

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.

Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.

For every non-edge $(u,v)$ there is a $k$-coloring such that $u$ and $v$ have the same color.

It is clear that every $k-1$-colorable graph has the $P_k$ property -- we can use the spare color for the non-edge and leave the other colors as they are.

Not every $k$-colorable graph has the $P_k$ property: $C_6$ is 2-colorable, but has not the $P_2$ property.

What is this property called?

EDIT: Some additional observations from last night.

If some $k$-colorable graph $G$ has not the $P_k$ property, then there is a non-edge $(u,v)$ in $G$ such that for every $k$-coloring of $G$ the colors of $u$ and $v$ are distinct. That means that every $k$-coloring of $G$ is a $k$-coloring of $G\cup(u,v)$.
Thus a graph $G$ has not the $P_k$ property iff we can add an edge with no effect on $k$-colorings and
$P_k$ property means that you cannot add an edge without losing some of the $k$-colorings.
So any $k$-colorable graph can be embedded into a graph with the $P_k$ property.
For example, if we start with $C_6$ we can add step-by-step 3 edges without any effect on 2-colorings; the resulting graph

has the $P_2$ property.

Entangled permutations of a multiset

2011-07-22T21:48:59Z

Let $M=\{1^{a_1},\dots,m^{a_m}\}$ be a multiset of numbers of cardinality $n$. Call a permutation of $M$ an $M$-word. We say that an $M$-word $w$ is entangled it cannot be written as a concatenation of two nonempty words $u,v$ such that $w=u.v$ and the sets of numbers/characters used in $u$ and $v$ are disjoint.

Examples: let $M=\{1^2,2^3,3^4\}$.

The words 122123333, 112323332 are not entagled:

122123333 = 12212.3333
112323332 = 11.2323332

The words 123213332, 311322233 are entangled.

Question: given a multiset $M$, how many entangled $M$-words are there?

Of course, it is possible to find a horrible-looking formula. But I feel that this problem should have a nice answer, maybe in a form of a generating function of some sort.

EDIT:

Another way how one can view entangled $M$-words: as lattice paths from $s=(0,\dots,0)$ to $e=(a_1,\dots,a_m)$ that avoid all extremal points of the box except for $s$ and $e$.

Answer by Gejza Jenča for Free, high quality mathematical writing online?

2011-05-25T19:05:22Z

Richard P. Stanley's Enumerative Combinatorics, volume 1, second edition is available at http://www-math.mit.edu/~rstan/ec/ec1/ .

Answer by Gejza Jenča for Generalizations of Boolean posets/lattices

2011-05-10T15:35:02Z

I think you could look at MV-algebras. They were introduced in the 50's by Chang in order to prove completness of the Lukasziewicz propositional many valued (MV) logic. From what I know, this class of algebras is the most special proper generalization of Boolean algebras that makes sense.

Every MV-algebra is a subdirect product of totally ordered MV-algebras; this is a direct generalization of the algebraic version of Stone's theorem. In the finite case, this reduces to the fact that every finite MV-algebra is isomorphic to a direct product of finite chains and vice versa. Even some of the more elaborate parts of the theory of Boolean algebras, like the Loomis-Sikorski theorem have their MV-algebraic versions.

As proved by Mundici in the 80's, MV-algebras are categorically equivalent to lattice ordered abelian groups with strong order unit.

The standard reference book for MV-algebras is this one.

Actions of $Z_n$ and actions of $Z_{n-1}$

2011-04-08T16:53:05Z

I am playing with some questions concerning connections between certain poset partitions and their linear extensions. This is not my usual playground, I just happened to stumble upon something.

When I was playing with these things, I came up with a very simple construction that I cannot find anywhere.I suspect that this construction is a minor particular case of something well known and much more general. It reminds of an equivariant map, but the group is not fixed here.

Let $n>2$, let $X$ be a finite set of cardinality $n$. Let $\oplus_n$ be an action of $Z_n$ on $X$ such that the action of $1$ is a cycle of length $n$. Pick $x\in X$ and let $\pi$ be a partition of the set $X$ such that $\{x,x\oplus_n 1\}$ is the only nonsingleton block of $\pi$.

In a very simple way, this gives rise to an action $\oplus_{n-1}$ of $Z_{n-1}$ on $\pi$ by ,,squeezing the action'' at $x$:

Put

$\{x,x\oplus_n 1\}\oplus_{n-1} 1=\{x\oplus_n 2\}$
$\{x\oplus_n(n-1)\}\oplus_{n-1} 1=\{x,x\oplus_n 1\}$
$\{y\}\oplus_{n-1} 1=\{y\oplus_n 1\}$ for any $y\neq x\oplus_n(n-1)$.

It can be visualized in a simple way by a digraph construction: if we identify the action of $1$ on $X$ with an oriented cycle, this construction corresponds to a contraction of an edge.

Has anyone seen this construction before? Is there any name for it?

Comment by Gejza Jenča

2013-04-19T06:43:47Z

Please, do not delete the answer. The last example is correct,I think.

Comment by Gejza Jenča

2013-04-19T06:08:47Z

The third example is not a functor, I think: take the path with 3 vertices $P_3$. It can be 2-colored, so there is a morphism into $K_2$. But there is no morphism $K_3\to K_2$.

Comment by Gejza Jenča

2013-04-18T20:19:59Z

I know that I am an not good at making examples but I do not understand how I could miss this one.

Comment by Gejza Jenča

2013-04-18T12:07:26Z

A trivial monad for a category $C$ is the one that arises from the adjoint pair of functors $(1_C,1_C)$. I do not understand what you mean by your second question.

Comment by Gejza Jenča

2012-03-17T09:22:28Z

The sole purpose of this comment is to contain the word "quasiorder" (an alternative name for preorders) -- greetings to the all-seeing eye of google.

Comment by Gejza Jenča

2012-03-16T17:41:09Z

Could not download it, but I found a direct link to pdf: intlpress.com/HHA/v12/n2/a7/v12n2a7.pdf

Comment by Gejza Jenča

2012-03-16T17:16:59Z

A very nice answer, thank you.

Comment by Gejza Jenča

2012-03-16T16:57:53Z

This is an extremely useful functor, when composed with other functors on the left. In combinatorics, one frequently takes an object (let us say a graph) constructs a poset (say a poset of certain sets of vertices) cuts off the bounds (to have a non-contractible space) and applies your Pos->Top functor. In some cases, the resulting space is a wedge of spheres and the dimension and/or the number of spheres express some properties of the original object.

Comment by Gejza Jenča

2012-03-16T16:47:19Z

@Martin Brandenburg: Maybe I misused the word "categorification": in the non-categorial mathematical literature a poset is a set (a 0-category) and the definition in my question is a 1-category: the elements become objects and the relations become arrows. It seems to me that your definition climbs one step higher.

Comment by Gejza Jenča

2012-02-28T22:29:24Z

Why not "hill" and "valley"?

Comment by Gejza Jenča

2011-10-15T08:24:09Z

@Joseph O'Rourke: Well, yes. I understand that as a subtle reminder that I should ask a slightly different question; something like "Has anyone seen anything like this before?".

Comment by Gejza Jenča

2011-07-27T18:17:27Z

@mhum: First impression is that nothing really nice happens, but I have to think about it more.

Comment by Gejza Jenča

2011-07-23T14:11:42Z

@Tony Hyunh: Please, do not delete the answer. The mistake is typical -- everyone I asked (3 people) made exactly this mistake at first before realizing that the problem is a bit more complicated. So I think it is better to keep the answer here, but to mark it as wrong.

Comment by Gejza Jenča

2011-07-23T12:35:06Z

For the record: the horrible-looking formula I found is based on the Moebius inversion of polynomial coefficients with respect to the poset of set partition of $\{1,\dots,m\}$ .

Comment by Gejza Jenča

2011-07-23T12:28:10Z

In your sum, you count the untangled permutation 112223333 twice, once for $X=\{1\}$ and second time for $X=\{1,2\}$.