{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T09:40:08Z","timestamp":1750498808332,"version":"3.41.0"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>Let <jats:italic>D(G)<\/jats:italic> be the smallest quantifier depth of a first-order formula which is true for a graph <jats:italic>G<\/jats:italic> but false for any other non-isomorphic graph. This can be viewed as a measure for the descriptive complexity of <jats:italic>G<\/jats:italic> in first-order logic.<\/jats:p>\n\t  <jats:p>We show that almost surely <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008376_inline1\">\n\t      <jats:alt-text>$D(G)=\\Theta(\\frac{\\ln n}{\\ln\\ln n})$<\/jats:alt-text>\n\t    <\/jats:inline-graphic>, where <jats:italic>G<\/jats:italic> is a random tree of order <jats:italic>n<\/jats:italic> or the giant component of a random graph <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008376_inline2\">\n\t      <jats:alt-text>$\\C G(n,\\frac cn)$<\/jats:alt-text>\n\t    <\/jats:inline-graphic> with constant <jats:italic>c<\/jats:italic>&lt;1. These results rely on computing the maximum of <jats:italic>D(T)<\/jats:italic> for a tree <jats:italic>T<\/jats:italic> of order <jats:italic>n<\/jats:italic> and maximum degree <jats:italic>l<\/jats:italic>, so we study this problem as well.<\/jats:p>","DOI":"10.1017\/s0963548306008376","type":"journal-article","created":{"date-parts":[[2007,1,23]],"date-time":"2007-01-23T15:57:49Z","timestamp":1169567869000},"page":"375-400","source":"Crossref","is-referenced-by-count":2,"title":["First-Order Definability of Trees and Sparse Random Graphs"],"prefix":"10.1017","volume":"16","author":[{"given":"TOM","family":"BOHMAN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALAN","family":"FRIEZE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TOMASZ","family":"\u0141UCZAK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OLEG","family":"PIKHURKO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CLIFFORD","family":"SMYTH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOEL","family":"SPENCER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OLEG","family":"VERBITSKY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,5,1]]},"reference":[{"key":"S0963548306008376_manual_ref-2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548306008376_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548306008376_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3423"},{"key":"S0963548306008376_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.04.003"},{"key":"S0963548306008376_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1029000098"},{"key":"S0963548306008376_manual_ref-11","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1120224721"},{"key":"S0963548306008376_manual_ref-13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511805967"},{"key":"S0963548306008376_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.003"},{"key":"S0963548306008376_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0720"},{"key":"S0963548306008376_manual_ref-1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100059995"},{"key":"S0963548306008376_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20049"},{"key":"S0963548306008376_manual_ref-7","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/038"},{"key":"S0963548306008376_manual_ref-10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.002"},{"key":"S0963548306008376_manual_ref-12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04538-1"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548306008376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:59:08Z","timestamp":1750496348000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548306008376\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0963548306008376"],"URL":"https:\/\/doi.org\/10.1017\/s0963548306008376","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2007,5]]}}}