User gejza jenča - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T20:36:40Z http://mathoverflow.net/feeds/user/4814 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130193/does-this-property-of-a-partially-ordered-set-have-a-name/130995#130995 Answer by Gejza Jenča for Does this property of a partially ordered set have a name? Gejza Jenča 2013-05-17T18:48:59Z 2013-05-17T18:48:59Z <p>In the world of partially ordered abelian groups, this is the <em>interpolation property</em>. These groups are called <em>partially ordered abelian groups with interpolation</em>, or simply <em>interpolation groups</em>. Intuitively, I think about them as "almost as nice as lattice ordered abelian groups".</p> <p>A simple example of a non-lattice ordered interpolation group is the set of all polynomial functions $\mathbb R\to\mathbb R$.</p> <p>Probably the most important subclass is the class of <em>dimension groups</em>. As proved by Effros, Handelman and Shen <a href="http://www.jstor.org/discover/10.2307/2374244?uid=3739024&amp;uid=2129&amp;uid=2&amp;uid=70&amp;uid=4&amp;sid=21102296591717" rel="nofollow">in 1980</a>, dimension groups classify the <a href="http://en.wikipedia.org/wiki/Approximately_finite_dimensional_C%2A-algebra" rel="nofollow">approximate finite dimensional $C^*$-algebras</a> (via the $K_0$ functor).</p> <p>I recommend this <a href="http://books.google.sk/books/about/Partially_Ordered_Abelian_Groups_With_In.html?id=dXUsGysPqRUC&amp;redir_esc=y" rel="nofollow">book by Goodearl</a> -- very readable, he is an excellent writer.</p> http://mathoverflow.net/questions/127949/is-there-any-nontrivial-monad-on-the-category-of-graphs Is there any nontrivial monad on the category of graphs? Gejza Jenča 2013-04-18T11:49:47Z 2013-04-19T21:49:50Z <p>The question is in the title, but let me specify what I mean by the category of graphs.</p> <p>In the context of this question, the category of graphs is the category of symmetric <em>irreflexive</em> relations. That means, not the category of symmetric <em>reflexive</em> relations. That means, no loops and at most one edge between vertices.</p> http://mathoverflow.net/questions/119726/discovering-and-selecting-conferences/120252#120252 Answer by Gejza Jenča for Discovering and selecting conferences Gejza Jenča 2013-01-29T20:07:53Z 2013-01-29T20:07:53Z <p>Conferences in General Algebra and Related Fields, maintained by <a href="http://spot.colorado.edu/~kearnes/conf.html" rel="nofollow">Keith Kearnes</a>.</p> <p>Links to Combinatorial Conferences, maintained by <a href="http://www.math.uiuc.edu/~west/meetlist.html" rel="nofollow">Douglas B. West</a>.</p> <p>Combinatorics and related conferences, maintained by <a href="http://www.maths.qmul.ac.uk/~pjc/bcc/conferences.html" rel="nofollow">Peter Cameron</a>.</p> http://mathoverflow.net/questions/119294/generating-function-of-a-regular-language/119298#119298 Answer by Gejza Jenča for Generating function of a regular language Gejza Jenča 2013-01-19T00:22:10Z 2013-01-19T00:22:10Z <p>This is basically equivalent for finding an <em>unambiguous regular expression</em> for the language. <a href="http://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous" rel="nofollow">This MO answer</a> explains how to do it, given an DFA $\mathcal A$.</p> <p>The rest is easy:</p> <ul> <li>replace $\emptyset$ by $0$</li> <li>replace $\epsilon$ by $1$</li> <li>replace any symbol with $x$</li> <li>replace concatenation with multiplication</li> <li>replace $\cup$ with $+$</li> <li>replace Kleene star with $1/1-f(x)$.</li> </ul> <p>Source: <a href="http://www.morris.umn.edu/academic/math/Ma4901/Sp2011/Final/BrianGoslinga-final.pdf" rel="nofollow">this paper</a>.</p> http://mathoverflow.net/questions/3044/tools-for-collaborative-paper-writing/108070#108070 Answer by Gejza Jenča for Tools for collaborative paper-writing Gejza Jenča 2012-09-25T16:28:31Z 2012-09-25T16:28:31Z <p><a href="https://gist.github.com/" rel="nofollow">Gist</a> 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. </p> <p>Feel free to edit <a href="https://gist.github.com/2725927" rel="nofollow">this gist</a>.</p> http://mathoverflow.net/questions/101014/fundamental-problems-whose-solution-seems-completely-out-of-reach/101155#101155 Answer by Gejza Jenča for Fundamental problems whose solution seems completely out of reach Gejza Jenča 2012-07-02T16:10:28Z 2012-07-02T16:10:28Z <p>Is every finite lattice a congruence lattice of a finite (universal) algebra? </p> <p>Astonishingly, by <a href="http://rd.springer.com/article/10.1007/BF02483080" rel="nofollow">Pálfy and Pudlák</a>, 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? </p> http://mathoverflow.net/questions/91377/the-category-of-posets The category of posets Gejza Jenča 2012-03-16T15:53:21Z 2012-03-19T14:56:37Z <p>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.</p> <p>Almost every introductory text in category theory contains following facts.</p> <ol> <li>The class of all posets with isotone maps is a category (called $Pos$).</li> <li>Every individual poset $P$ is a category, with comparable pairs $x\leq y$ as arrows. This can be called "a categorified poset".</li> </ol> <p>Sometimes, product and coproduct in $Pos$ is characterized and (less frequently) it is pointed out that a <a href="http://en.wikipedia.org/wiki/Galois_connection" rel="nofollow">Galois connection</a> 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. </p> <p>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.</p> <p>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 <a href="http://www.cody.it/pietro.php?piepage=research" rel="nofollow">here</a>, which is from 2004 and characterizes (co)equalizers in $Pos$.</p> <p>Does anyone know about some other sources of information about $Pos$ from the category-theoretic viewpoint? Specifically, I am looking for things like</p> <ul> <li>useful functors to $Pos$ and from $Pos$,</li> <li>pullbacks, pushouts and other universal constructions in $Pos$,</li> <li>examples of adjoint functors, applications of Yoneda lemma etc. </li> </ul> http://mathoverflow.net/questions/78149/what-is-this-subclass-of-k-colorable-graphs-called What is this subclass of $k$-colorable graphs called? Gejza Jenča 2011-10-14T16:51:54Z 2011-10-15T17:45:13Z <p>The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.</p> <p>Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.</p> <blockquote> <p>For every non-edge $(u,v)$ there is a $k$-coloring such that $u$ and $v$ have the same color.</p> </blockquote> <p>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.</p> <p>Not every $k$-colorable graph has the $P_k$ property: $C_6$ is 2-colorable, but has not the $P_2$ property.</p> <p>What is this property called?</p> <p><strong>EDIT:</strong> Some additional observations from last night.</p> <ul> <li>If some $k$-colorable graph $G$ has <em>not</em> 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)$. </li> <li>Thus a graph $G$ has <em>not</em> the $P_k$ property iff we can add an edge with no effect on $k$-colorings and</li> <li>$P_k$ property means that you cannot add an edge without losing some of the $k$-colorings.</li> <li>So any $k$-colorable graph can be embedded into a graph with the $P_k$ property.</li> <li>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</li> </ul> <p><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Utility_graph.circo.svg/150px-Utility_graph.circo.svg.png"> </p> <p>has the $P_2$ property.</p> http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset Entangled permutations of a multiset Gejza Jenča 2011-07-22T21:48:59Z 2011-07-24T10:04:14Z <p>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 <em>entangled</em> 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.</p> <p>Examples: let $M=\{1^2,2^3,3^4\}$.</p> <p>The words 122123333, 112323332 are not entagled:</p> <ul> <li>122123333 = 12212.3333</li> <li>112323332 = 11.2323332</li> </ul> <p>The words 123213332, 311322233 are entangled.</p> <p>Question: given a multiset $M$, how many entangled $M$-words are there?</p> <p>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.</p> <p>EDIT: </p> <p>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$.</p> http://mathoverflow.net/questions/1722/free-high-quality-mathematical-writing-online/65981#65981 Answer by Gejza Jenča for Free, high quality mathematical writing online? Gejza Jenča 2011-05-25T19:05:22Z 2011-05-25T19:05:22Z <p>Richard P. Stanley's Enumerative Combinatorics, volume 1, second edition is available at <a href="http://www-math.mit.edu/~rstan/ec/ec1/" rel="nofollow">http://www-math.mit.edu/~rstan/ec/ec1/</a> .</p> http://mathoverflow.net/questions/6538/generalizations-of-boolean-posets-lattices/64508#64508 Answer by Gejza Jenča for Generalizations of Boolean posets/lattices Gejza Jenča 2011-05-10T15:35:02Z 2011-05-10T15:35:02Z <p>I think you could look at <a href="http://en.wikipedia.org/wiki/MV-algebra" rel="nofollow">MV-algebras</a>. They were <a href="http://www.ams.org/mathscinet-getitem?mr=0094302" rel="nofollow">introduced in the 50's by Chang</a> in order to prove completness of the Lukasziewicz propositional <em>many valued</em> (MV) logic. From what I know, this class of algebras is the most special proper generalization of Boolean algebras that makes sense.</p> <p>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.</p> <p>As proved by Mundici in the 80's, MV-algebras are categorically equivalent to lattice ordered abelian groups with strong order unit.</p> <p>The standard reference book for MV-algebras is <a href="http://www.amazon.com/Algebraic-Foundations-Many-Valued-Reasoning-Trends/dp/0792360095" rel="nofollow">this one</a>.</p> http://mathoverflow.net/questions/61081/actions-of-z-n-and-actions-of-z-n-1 Actions of $Z_n$ and actions of $Z_{n-1}$ Gejza Jenča 2011-04-08T16:53:05Z 2011-04-20T11:59:30Z <p>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.</p> <p>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. </p> <p>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$.</p> <p>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$:</p> <p>Put</p> <ul> <li>$\{x,x\oplus_n 1\}\oplus_{n-1} 1=\{x\oplus_n 2\}$</li> <li>$\{x\oplus_n(n-1)\}\oplus_{n-1} 1=\{x,x\oplus_n 1\}$</li> <li>$\{y\}\oplus_{n-1} 1=\{y\oplus_n 1\}$ for any $y\neq x\oplus_n(n-1)$.</li> </ul> <p>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. </p> <p>Has anyone seen this construction before? Is there any name for it?</p> http://mathoverflow.net/questions/127949/is-there-any-nontrivial-monad-on-the-category-of-graphs/127954#127954 Comment by Gejza Jenča Gejza Jenča 2013-04-19T06:43:47Z 2013-04-19T06:43:47Z Please, do not delete the answer. The last example is correct,I think. http://mathoverflow.net/questions/127949/is-there-any-nontrivial-monad-on-the-category-of-graphs/127954#127954 Comment by Gejza Jenča Gejza Jenča 2013-04-19T06:08:47Z 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$. http://mathoverflow.net/questions/127949/is-there-any-nontrivial-monad-on-the-category-of-graphs/127952#127952 Comment by Gejza Jenča Gejza Jenča 2013-04-18T20:19:59Z 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. http://mathoverflow.net/questions/127949/is-there-any-nontrivial-monad-on-the-category-of-graphs Comment by Gejza Jenča Gejza Jenča 2013-04-18T12:07:26Z 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. http://mathoverflow.net/questions/91377/the-category-of-posets/91391#91391 Comment by Gejza Jenča Gejza Jenča 2012-03-17T09:22:28Z 2012-03-17T09:22:28Z The sole purpose of this comment is to contain the word &quot;quasiorder&quot; (an alternative name for preorders) -- greetings to the all-seeing eye of google. http://mathoverflow.net/questions/91377/the-category-of-posets/91393#91393 Comment by Gejza Jenča Gejza Jenča 2012-03-16T17:41:09Z 2012-03-16T17:41:09Z Could not download it, but I found a direct link to pdf: <a href="http://www.intlpress.com/HHA/v12/n2/a7/v12n2a7.pdf" rel="nofollow">intlpress.com/HHA/v12/n2/a7/v12n2a7.pdf</a> http://mathoverflow.net/questions/91377/the-category-of-posets/91391#91391 Comment by Gejza Jenča Gejza Jenča 2012-03-16T17:16:59Z 2012-03-16T17:16:59Z A very nice answer, thank you. http://mathoverflow.net/questions/91377/the-category-of-posets/91381#91381 Comment by Gejza Jenča Gejza Jenča 2012-03-16T16:57:53Z 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-&gt;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. http://mathoverflow.net/questions/91377/the-category-of-posets Comment by Gejza Jenča Gejza Jenča 2012-03-16T16:47:19Z 2012-03-16T16:47:19Z @Martin Brandenburg: Maybe I misused the word &quot;categorification&quot;: 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. http://mathoverflow.net/questions/28612/do-names-given-to-math-concepts-have-a-role-in-common-mistakes-by-students/28625#28625 Comment by Gejza Jenča Gejza Jenča 2012-02-28T22:29:24Z 2012-02-28T22:29:24Z Why not &quot;hill&quot; and &quot;valley&quot;? http://mathoverflow.net/questions/78149/what-is-this-subclass-of-k-colorable-graphs-called Comment by Gejza Jenča Gejza Jenča 2011-10-15T08:24:09Z 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 &quot;Has anyone seen anything like this before?&quot;. http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset Comment by Gejza Jenča Gejza Jenča 2011-07-27T18:17:27Z 2011-07-27T18:17:27Z @mhum: First impression is that nothing really nice happens, but I have to think about it more. http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset/71058#71058 Comment by Gejza Jenča Gejza Jenča 2011-07-23T14:11:42Z 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. http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset Comment by Gejza Jenča Gejza Jenča 2011-07-23T12:35:06Z 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\}$ . http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset/71058#71058 Comment by Gejza Jenča Gejza Jenča 2011-07-23T12:28:10Z 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\}$.