{"entities":{"Q793058":{"pageid":794906,"ns":120,"title":"Item:Q793058","lastrevid":64416900,"modified":"2026-04-11T19:43:38Z","type":"item","id":"Q793058","labels":{"en":{"language":"en","value":"On the minimum order of graphs with given semigroup"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3855163"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$36F4733D-6787-42ED-A3B7-F7A087BACC5A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efb043f34ed86fc8d0054d6777faa6de16573900","datavalue":{"value":{"text":"On the minimum order of graphs with given semigroup","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793058$F196074F-AB7B-4922-ACE9-F15A16B81E78","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a2f5e2a5ca90c040d1bbad143586cf9875289705","datavalue":{"value":"0538.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$E1736107-276C-4417-BC09-3AEA81ECCE38","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c120a45d6e9f14cfaa24cbe6c4079d4232c72b61","datavalue":{"value":"10.1016/0095-8956(84)90021-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$FAFEE936-C91B-410A-80AF-B2E1A3A64838","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"764f84a646c763434432ad369d0bc1a8abdf96a9","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$B3DA7BF1-F7F4-407F-B955-F7CC572DA3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$B38B3E28-E09E-4094-B6EA-862432023523","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$471B97B8-7C1A-470B-8AF0-1F40EE62B805","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q793058$C050D157-4754-476C-9DD8-32B168D6C2ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e72d85422dffc9d9932d6b7bcc7d6c0e783ecb1","datavalue":{"value":"Denote by M(n) the smallest positive integer such that for every n- element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that \\(\\sqrt{2}(1+o(1)n\\sqrt{\\log_ 2n}\\leq M(n)\\leq n\\cdot \\sqrt{2n}+O(n).\\) The same lower-bound and \\(12n \\log_ 2n+n\\) as an upper bound are given with respect to monoids which are 3-nilpotent (i.e. \\(xyz=o\\) for a two sided zero element o and for all x,y,\\(z\\neq 1)\\). For k-uniform hypergraphs an upper bound is shown to be 3n for \\(k=3,4,..\\). and \\(n\\geq 6k+6.\\) Moreover there are given estimates of the number of graphs with n vertices and a given endomorphism monoid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q793058$B35DFC7B-9DFE-4E86-92AA-078ECF1E3A4A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$2D055284-76A8-4ED9-A9C6-8A8F8650FDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$CDF16CA1-7C03-4A1B-8E13-40E71729A376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"328feb8b87ded0da841a7444b6ecdb385c89ee49","datavalue":{"value":"20M30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$469584B6-A26C-49FD-9EE6-3659FC4F00DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9fe4cec37a422f5744e3cd50af2d00536dc52ce","datavalue":{"value":"3855163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$C0B8B1D9-A04E-4B5D-ADAA-938F7B7A5DCD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a621b385d2331ab32748ff7035096a56396f53d5","datavalue":{"value":"uniform hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q793058$361973CC-699E-4A51-9374-7A397E4C709E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e86038b670025220fd28eec2af67f76172dada4","datavalue":{"value":"endomorphism monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q793058$1895A84D-3FCE-47BF-ACE8-9EA1EAEF1B07","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"85e4af3c816f7ac40605750dbfec22d9e5ba7cdc","datavalue":{"value":{"entity-type":"item","numeric-id":207731,"id":"Q207731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$9997EE17-DBB9-41AE-891F-F4BA6AB31356","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$317E553F-2F1C-40DD-B32D-811CB5D5781C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"94b4c57b1334658c2814bcc72e3cafb98ffd52d5","datavalue":{"value":"https://doi.org/10.1016/0095-8956(84)90021-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q793058$7CE15D39-4D60-4889-A6F2-EF1816D9503D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c4925676c97b4ef1ba2a1839ac42e620f052075b","datavalue":{"value":"W2034331627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793058$932926DB-1F2D-4F26-93D0-C158DFF116EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"653255262a3836f3f86ca23913d06a64bcfbf46b","datavalue":{"value":{"entity-type":"item","numeric-id":4068752,"id":"Q4068752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$25A17765-88CA-4975-9D48-EEABB9097854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41d4af741fdcfa9bba23d0a8bb8e1b54dceeb59b","datavalue":{"value":{"entity-type":"item","numeric-id":1251669,"id":"Q1251669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$3EB1A112-E07E-483B-B699-8C5690CC47F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50cfad429314e1605f6ade5a2c59b3e9f12f443e","datavalue":{"value":{"entity-type":"item","numeric-id":1076512,"id":"Q1076512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$B126AD55-4C6B-424E-BFBC-876C334DF4B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d34c2eed9ef5fc3d358f32fa8872708612a0fa4f","datavalue":{"value":{"entity-type":"item","numeric-id":5834591,"id":"Q5834591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$1B4884E1-EE40-4CCD-9753-ECEFA6CF5971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$2A94A444-A4D7-443E-BFAB-7BD347AF5BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fca512bd62ef81317baaf07336a09e35ab66e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5789964,"id":"Q5789964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$AEFAA7FE-4720-4BEA-BF6D-FC7B116A859E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43c356c01816cbbc7bdabae243ae703945f5fe3e","datavalue":{"value":{"entity-type":"item","numeric-id":5728982,"id":"Q5728982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$F1531213-200D-49C4-9422-54369C0D6E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$42FAAF92-E040-4B1F-847A-0564FEABE877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f512d3044d87913829cd345dbca09d60481c7fa","datavalue":{"value":{"entity-type":"item","numeric-id":5572358,"id":"Q5572358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$A0C84705-950B-4594-A795-E2E60DD02171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f8b426f4a8afe5c53630d0f701f0de61dbaf2b2","datavalue":{"value":{"entity-type":"item","numeric-id":2394311,"id":"Q2394311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$9FB50760-C2C6-41F4-B44B-B288FC8A51D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5193437090ba18c902ca94c434c247b3995ab17e","datavalue":{"value":{"entity-type":"item","numeric-id":5611042,"id":"Q5611042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$010C0450-B357-47F0-9EB2-90CAA9DF063A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c32f7218936792e54e54fa472b414c278db77e58","datavalue":{"value":{"entity-type":"item","numeric-id":4087203,"id":"Q4087203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$DB9D5B6B-708E-4949-8976-6D2BD77B8A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$54357A15-6573-42E5-81A3-C4775A99F1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dacc118959ac4406901793fdc048b61fa833ad70","datavalue":{"value":{"entity-type":"item","numeric-id":3208855,"id":"Q3208855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793058$4B74BA1F-16F8-4387-88F0-77FB8D7EE3EA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66c1ecea08e70bbe005578a58807994275090e68","datavalue":{"value":{"entity-type":"item","numeric-id":3652555,"id":"Q3652555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fcaf9d52095ac25fd884519d523e28dbefb84e8","datavalue":{"value":{"amount":"+0.8661003112792969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793058$A77C2319-1DB0-40CF-9453-A7F3B2F82FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffedd99b4c67498a5eb389ba0c27ccd8bca277ae","datavalue":{"value":{"entity-type":"item","numeric-id":960940,"id":"Q960940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0d5f43bca0db6d29611578b538dde9b7371aec8","datavalue":{"value":{"amount":"+0.8599675893783569","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793058$1D7085EF-234E-499F-B9F0-A4650944554F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"866f6f0fd9ae777db39fb74f3a04ad3e5c145706","datavalue":{"value":{"entity-type":"item","numeric-id":3398319,"id":"Q3398319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b794ac3768dda9847d617e6662bbefc39c0ee8d","datavalue":{"value":{"amount":"+0.7987750768661499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793058$FA62EB1D-5CCD-4C79-8798-0CE31F0C31DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06376e705d336085a9852ab0e6e64dca7befd774","datavalue":{"value":{"entity-type":"item","numeric-id":4576673,"id":"Q4576673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"759f75c7ed7019483ba3c30746bc6f93677f2d32","datavalue":{"value":{"amount":"+0.7977381348609924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793058$18265E51-AA62-4FBF-8FBD-BF05397D4BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91ba092522e5162dcfb2d115f5bc65249dd0dab5","datavalue":{"value":{"entity-type":"item","numeric-id":4982506,"id":"Q4982506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cebfebee68acd619bb821aae24600b4d793475fa","datavalue":{"value":{"amount":"+0.7870480418205261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793058$44678C34-A614-4DD1-B609-CD0D6287A6FE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the minimum order of graphs with given semigroup","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_minimum_order_of_graphs_with_given_semigroup"}}}}}