{"entities":{"Q1972678":{"pageid":1983420,"ns":120,"title":"Item:Q1972678","lastrevid":82135982,"modified":"2026-05-06T20:11:18Z","type":"item","id":"Q1972678","labels":{"en":{"language":"en","value":"Constrainted graph processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1431769"}},"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":"Q1972678$DC5E0E3C-91A4-47D4-9AB4-13E3EE2B15EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ef02aa52ee2e78cb187b0a2b75cf3a900aa6ac0","datavalue":{"value":{"text":"Constrainted graph processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972678$88FF6099-8753-48C8-9F2F-32706C9CF67B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9fbecf626f69ee89f7235446a4a0b50a16e76ab9","datavalue":{"value":"0939.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972678$6A8DD9A8-9477-47AF-91A0-F355A4B10100","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972678$8B02318F-DC17-487B-A2EB-CE08734E7DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac63f30566cbd710d3cc43a4effc13b649654e60","datavalue":{"value":{"entity-type":"item","numeric-id":243307,"id":"Q243307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972678$C0A84E00-A02F-4B4F-8E36-65704A32B1A7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972678$EA6EA796-5F46-4748-B431-46DB227DCDD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd2d1fe82fa6e2c6e97c965e0ca8e16ed58495a5","datavalue":{"value":{"time":"+2000-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972678$568D8A22-1AA5-4936-8CFF-C55E5D7BC525","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"430b00ff3e6d444a1e0bedd2d0ecd8774be42558","datavalue":{"value":"https://eudml.org/doc/120358","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972678$C7F11F77-C16D-4851-AB73-2143C46CF0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6511fdc4630d4dbcc4e0900c626029c1da811aa","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r18.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972678$245B20B9-95A2-48F7-AF10-5A20142B4EE2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bf86d54fabf82530bd4c7a079317a04ba33c3045","datavalue":{"value":"Summary: Let \\(\\mathcal Q\\) be a monotone decreasing property of graphs \\(G\\) on \\(n\\) vertices. \\textit{P. Erd\u0151s, S. Suen} and \\textit{P. Winkler} [Random Struct. Algorithms 6, No. 2-3, 309-318 (1995; Zbl 0820.05054)]\\ introduced the following natural way of choosing a random maximal graph in \\(\\mathcal Q\\): start with \\(G\\) the empty graph on \\(n\\) vertices. Add edges to \\(G\\) one at a time, each time choosing uniformly from all \\(e\\in G^c\\) such that \\(G+e\\in \\mathcal Q\\). Stop when there are no such edges, so the graph \\(G_\\infty\\) reached is maximal in \\(\\mathcal Q\\). Erd\u0151s, Suen and Winkler asked how many edges the resulting graph typically has, giving good bounds for \\(\\mathcal Q=\\) \\{bipartite graphs\\} and \\(\\mathcal Q=\\) \\{triangle free graphs\\}. We answer this question for \\(C_4\\)-free graphs and for \\(K_4\\)-free graphs, by considering a related question about standard random graphs \\(G_p\\in \\mathcal G(n,p)\\). The main technique we use is the `step by step' approach of our paper [(*) Colorings generated by monotone properties, Random Struct. Algorithms 12, No. 1, 1-25 (1998; Zbl 0894.05043)]. We wish to show that \\(G_p\\) has a certain property with high probability. For example, for \\(K_4\\)-free graphs the property is that every `large' set \\(V\\) of vertices contains a triangle not sharing an edge with any \\(K_4\\) in \\(G_p\\). We would like to apply a standard Martingale inequality, but the complicated dependence involved is not of the right form. Instead we examine \\(G_p\\) one step at a time in such a way that the dependence on what has gone before can be split into `positive' and `negative' parts, using the notions of up-sets and down-sets. The relatively simple positive part is then estimated directly. The much more complicated negative part can simply be ignored, as shown in (*).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972678$822D2484-9E94-440D-A029-B8C4E101CDEA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972678$4CD9C8BE-C022-409D-A3C2-99A147C4A690","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2220e2dd520a251f8c10b6a9ac6d5d6bc831ac0","datavalue":{"value":"1431769","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972678$9C8DB0A8-F195-409B-9FB2-0DE6170539B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972678$83718C10-B40F-4414-9C2E-777B413348E6","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":"Q1972678$7FB2ADDF-87EB-4D4E-AFAC-73295706BD1B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"96f9250bc73e50ee45acdbbb334847b3e47a8781","datavalue":{"value":"bafkreiagfwxhi3v7c5aubayaqx6d6okawlxxkyw4uh3nxo6ozyidqxfavu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972678$4351AA3E-2EB2-45E4-A861-887CD59752A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"711f886426b20ebbfcd810bc146675999490e9fd","datavalue":{"value":{"entity-type":"item","numeric-id":5415596,"id":"Q5415596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0325bc16ca9bb4937224482160ba9610f78f0131","datavalue":{"value":{"amount":"+0.7988864183425903","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":"Q1972678$7F625BE1-88F9-4D21-B4F0-DEEB2402FE76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bcb9a54c44a859ef6f6b2c1db5b4a2d8950ba2c","datavalue":{"value":{"entity-type":"item","numeric-id":3549484,"id":"Q3549484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7924826920898bf7206092a70a67f08d02e3b728","datavalue":{"value":{"amount":"+0.7969841957092285","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":"Q1972678$C8545CA3-5DC5-4B3A-BDA8-2773EC233087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfbc3f4c79733c8e94abfab4825124b77698b5f5","datavalue":{"value":{"entity-type":"item","numeric-id":3103637,"id":"Q3103637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"335ac055501b410a112f747a5fb248045354d9b6","datavalue":{"value":{"amount":"+0.7913752794265747","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":"Q1972678$0AED6E68-929F-421E-ADBE-0EE5C1FB61B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6364f00c3d3b057e8d1087c4e59f796a2255e3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1023043,"id":"Q1023043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceb065841b872ad45df6ad6718866e72363717a7","datavalue":{"value":{"amount":"+0.7775536775588989","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":"Q1972678$F7F54CBD-FA91-409F-9593-D1507A7AE3D5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Constrainted graph processes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Constrainted_graph_processes"}}}}}