User vzn - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:53:24Z http://mathoverflow.net/feeds/user/20793 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence compression of a Turing machine run sequence vzn 2012-01-21T23:22:15Z 2013-04-30T09:07:31Z <p>consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as the sequence of state-symbol pairs that ensue in the computation. call the $i$th ensuing state $s'_i$ and the $i$th ensuing symbol $a'_i$. </p> <p>then the run sequence is the sequence $[(s'_1,a'_1),(s_2,a'_2),(s'_3,a'_3),...]$. or equivalently of composite symbol-pairs $[s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$. if the computation terminates after $z$ steps then $i\leq z$. (note the run sequence is also defined for sequences that do not terminate, in that case its an infinitely long sequence but a (long?) finite initial subsequence alone can be considered.)</p> <p>now consider large run sequences for large inputs and a large $z$. ie consider the question for recursive machines only.</p> <blockquote> <p><strong>question</strong>: what can be said about the <em>compressibility</em> of the Turing machine run sequence?</p> </blockquote> <p>"compressible" means: is there an algorithm that can be used in the sense of data compression.</p> <p>my current suspicion (without proof so far) is that if the machine is recursive and runs in some time $O(f(m))$ or (space $O(h(m))$ resp.) where $f(m)$ is some "std" function of input length $m$ say logarithmic, polynomial, exponential etc. then the run sequence is indeed compressible in some sense.</p> <p>does anyone know a similar formulation of this problem that can be found in the literature or is studied somewhere? thx!</p> <p><sup> motivation: a possible useful formulation for understanding separations between complexity classes. think this problem might help bridge relationships between time and space complexity separations, tradeoffs etc. </sup></p> http://mathoverflow.net/questions/125870/counting-k-cliques-not-also-k1-on-random-graphs counting k-cliques not also (k+1) on random graphs vzn 2013-03-29T03:26:30Z 2013-03-29T17:04:40Z <p>consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges. </p> <blockquote> <p>looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+1)$-clique. </p> </blockquote> <p>looked at some of the Erdos-Renyi random graph theory and related formulas but did not see this case covered so far. an estimate may be ok. also if this is used in a paper somewhere, that would be useful to know.</p> <p><strong>edit</strong> as Erdos-Renyi theory &amp; a comment points out the critical point for detection of a $k$-clique is at $k=\log(n)$ where the probability goes from $P&lt;0.5$ to $P>0.5$. it would be very interesting if there was a formula that could be derived independent of these regions (once called "subcritical, critical, supercritical"), but am seeking the answer for $k \approx \log(n)$ in particular.</p> <p>background/motivation: question inspired by similar constructions in theoretical computer science circuit theory proofs/theorems.</p> http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Collatz conjecture— finite state machine transducer construction, origination? vzn 2013-03-03T20:27:43Z 2013-03-03T20:27:43Z <p>wikipedia has an entry on the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow">Collatz conjecture</a> with a section on <a href="http://en.wikipedia.org/wiki/Collatz_conjecture#As_an_abstract_machine_that_computes_in_base_two" rel="nofollow">As an abstract machine that computes in base two</a>. this apparently describes a construction of a <a href="http://en.wikipedia.org/wiki/Finite_state_transducer" rel="nofollow">FSM transducer</a> computing sequential iterates starting from lsb to msb (least sig. bit to most sig. bit). [this is more a TCS, theoretical computer science construction.] however, there is no specific ref cited.</p> <blockquote> <p>does anyone know where this FSM iterate transducer construction appears, or first appeared in the literature?</p> </blockquote> <p>note, there is some relation to ref [4].</p> <p><sup>[ps, have some apparently new/possibly groundbreaking results related to this construction &amp; intend to write it up on a blog, may edit this post later to incl the ref.]</sup></p> <p>[1] <a href="http://www.amazon.com/The-Ultimate-Challenge-3x-Problem/dp/0821849409/" rel="nofollow">The ultimate challenge: the 3x+1 problem</a>, Lagarias</p> <p>[2] <a href="http://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful" rel="nofollow">what is the nearest problem to the collatz conjecture that has been successfully resolved</a>, tcs.se</p> <p>[3] <a href="http://arxiv.org/pdf/math/0309224.pdf" rel="nofollow">The 3x + 1 Problem: An Annotated Bibliography</a>, Lagarias, arxiv</p> <p>[4] Jeffrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Au- tomata, Bulletin of the EATCS (European Association for Theoretical Computer Sci- ence), No. 46, 1991, pp. 182–185.</p> http://mathoverflow.net/questions/86391/what-is-this-small-3-element-quasigroup-what-is-it-used-for what is this small 3 element quasigroup & what is it used for vzn 2012-01-22T18:02:59Z 2013-01-27T19:46:44Z <p>this following multiplication table arises in a deep area of theoretical computer science proofs eg complexity theory &amp; am looking at it more in isolation or outside of TCS. looked for this multiplication table on wikipedia as some mathematically recognized or used object but couldnt find it. does it show up elsewhere? </p> <pre><code> a b c a a c a b c b b c a b c </code></pre> <p>(prior comments point out it is <em>not</em> a group or semigroup but seem to confirm its at least a quasigroup). are there applications of it? what can it be used for? am esp interested in some way of implementing a boolean logic with it. (however if there was some way to link it to group theory that would be very interesting too). "c" may or may not be the empty element. thx</p> <p>note— may edit this question later to describe at least one very specific case where it appears in theoretical computer science, but for now am leaving it open so as not to bias possible answers. question [1] on cs.se points to one possible application ie trinary valued circuit logic.</p> <p>[1] <a href="http://cs.stackexchange.com/questions/9211/building-functionally-complete-boolean-circuits-out-of-trinary-logic" rel="nofollow">building functionally complete boolean circuits out of trinary logic</a></p> http://mathoverflow.net/questions/115356/experimental-mathematics-how-are-floating-point-equations-discovered-converted experimental mathematics-- how are floating point equations discovered/converted to exact equations vzn 2012-12-04T04:55:54Z 2012-12-04T08:09:16Z <p>the 2005 AMS article/survey on experimental mathematics[1] by Bailey/Borwein mentions many remarkable successes in the field including new formulas for $\pi$ that were discovered via the PSLQ algorithm as well as many other examples. however, it appears to glaringly leave out any description of the crucial step. it goes from discussing large accuracy floating point operations/formulas to stating the <em>exact</em> theoretical formulas with no discussion of the intermediate step(s).</p> <blockquote> <p>suppose a floating point formula is found experimentally that holds for many finite points of the formula to a high degree of precision. how is it proven that the abstract algebraic formula which does not use floating point arithmetic with finite accuracy is correct?</p> </blockquote> <p>this seems to relate to <em>induction</em>. of course a formula can hold for a finite number of points or finite precision but then fail for more points or "infinite" precision. is there any discussion that focuses on this step/conversion/aspect? of course a virtually identical/analogous issue arises in statistics with curve fitting and the danger of "overfitting".</p> <p>[1] <a href="http://www.ams.org/notices/200505/fea-borwein.pdf" rel="nofollow">Experimental Mathematics: Examples, Methods and Implications</a> by Bailey/Borwein, notes of the AMS, 2005</p> http://mathoverflow.net/questions/108655/hypergraph-cartesian-join-operation-over-same-vertex-set hypergraph cartesian join operation (over same vertex set) vzn 2012-10-02T17:15:26Z 2012-10-06T18:52:34Z <p>consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph $H_3=H_1 \sqcup H_2 = (V, \mathscr{E}_1 \times \mathscr{E}_2)$ where "$\times$" is the cartesian join over edge sets. am using the "$\sqcup$" join operator basically as defined in [1], a web page by B.Lynn about ZDDs (a variant of BDD, binary decision diagrams), but havent seen that notation used in a paper so far. BDDs/ZDDs are an equivalent representation system for set families or hypergraphs. ZDDs generally more efficiently model <em>"sparse"</em> BDDs without all variable references.</p> <p>this cartesian join appears not to have been studied much or be much related to hypergraph products (of which there is significant recent material &amp; research) because hypergraph products are all defined over two different vertex sets $V_1, V_2$ and are built out of the cartesian join of the <em>vertex sets</em> (<em>not</em> the edge sets).</p> <p>Knuth has enthusiastically investigated ZDDs [2],[3] &amp; has dedicated a significant section of his <em>Art of computer programming vol4.1</em> to the subject (30pp and 70 exercises):</p> <p><em>Such operations form a "family algebra," and there are interesting algorithms to implement the operations of family algebra as operations on ZDDs. Family algebra is a relatively new topic that is just beginning to be understood.</em></p> <p>this cartesian join operation in ZDDs appears to have been 1st implemented by Minato, an originator of ZDD operations. see p10 of [4] where it is called the "cartesian product set P*Q" and was apparently 1st introduced in [6] p7.</p> <blockquote> <p>what are some other references on or applications of this hypergraph cartesian join operation?</p> </blockquote> <p>am particularly interested in its similarities to products and factoring incl decomposition algorithms etc. </p> <p><hr> [1] <a href="http://crypto.stanford.edu/pbc/notes/zdd/family.xhtml" rel="nofollow">Families of sets/multiple families</a> by B.Lynn on ZDDs</p> <p>[2] Katayanagi prize, <a href="http://www.cs.cmu.edu/~katayanagi/2009/knuth_abstract.html" rel="nofollow">ZDD Structures and Families of Sets, Donald E. Knuth</a></p> <p>[3] <a href="http://www.cs.ox.ac.uk/news/2-full.html" rel="nofollow">Fun with ZDDs talk by Knuth</a></p> <p>[4] <a href="http://www.jst.go.jp/sicp/ws2010_austria/presentation/presentation_22.pdf" rel="nofollow">ZDD and its applications to intelligent processing</a> slides by Minato</p> <p>[5] <a href="http://www-erato.ist.hokudai.ac.jp/docs/tcstr-minato.pdf" rel="nofollow">Recent and future work on decision diagrams and discrete structure manipulation</a> by Minato</p> <p>[6] <a href="http://eprints2008.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf" rel="nofollow">Zero suppressed BDDs and their applications</a> by Minato</p> http://mathoverflow.net/questions/108208/products-factoring-of-two-hypergraphs-with-same-vertex-set products/factoring of two hypergraphs with same vertex set? vzn 2012-09-27T04:14:26Z 2012-09-27T04:14:26Z <p>all the basic products for graphs have been extended to hypergraphs[1].</p> <blockquote> <p>is there a concept of a product of hypergraphs with the same vertex set? has this been studied?</p> </blockquote> <p>normally the hypergraph product is between two hypergraphs $H_1 = (V_1, \mathscr{E}_1), H_2 = (V_2, \mathscr{E}_2)$. am asking about the case $V_1=V_2$. (have an idea for a defn of this but am looking for any other preexisting cases first. esp interested in factoring)</p> <p>[1] <a href="http://lips.informatik.uni-leipzig.de/files/diplom_0.pdf" rel="nofollow">Hypergraph products</a> by Hellmuth</p> <p>[2] mathoverflow, <a href="http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs" rel="nofollow">What are the Applications of Hypergraphs</a></p> http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown/107703#107703 Answer by vzn for What is the shortest program for which halting is unknown? vzn 2012-09-20T17:48:05Z 2012-09-20T17:56:32Z <p>this question is apparently closely related to Wolframs research program of determining whether "small" Cellular Automata [CAs][1] are Turing Complete. if the CA is proved Turing Complete then by mapping with Turings halting problem, there exists an input for which termination of the CA cannot be proven. but also determining whether the CA is Turing complete can be very difficult and there are several so-far-indeterminate cases. a case where it succeeded but with a very complex proof is [2], some further details of the dynamics in [4]. see also [5] for a writeup of an ambitious somewhat recent "major attack" on the busy beaver problem that superseded many prior results. and there is also a related long tradition of research for finding small state universal TMs[3,6] probably dating to the ~1960s including results by Marvin Minsky. re Collatz conjecture candidate &amp; a boundary with "nearby" problems similar to Conway-type, see also [7]</p> <p>[1] <a href="http://en.wikipedia.org/wiki/Elementary_cellular_automaton" rel="nofollow">Elementary cellular automata, wikipedia</a></p> <p>[2] <a href="http://en.wikipedia.org/wiki/Rule_110" rel="nofollow">Rule 110, wikipedia</a></p> <p>[3] tcs.se, <a href="http://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine" rel="nofollow">whats the simplest noncontroversial 2 state universal TM</a></p> <p>[4] tcs.se <a href="http://cstheory.stackexchange.com/questions/11002/initial-conditions-for-universal-rule-110" rel="nofollow">initial conditions for rule 110</a></p> <p>[5] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.3485" rel="nofollow">New-Millenium Attack on the Busy Beaver Problem</a> by Ross et al</p> <p>[6] <a href="http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf" rel="nofollow">The complexity of small universal Turing machines: a survey</a> Woods &amp; Neary</p> <p>[7] tcs.se, <a href="http://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful" rel="nofollow">whats the nearest problem to the Collatz conjecture thats been successfully resolved?</a></p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/107649#107649 Answer by vzn for What are the Applications of Hypergraphs vzn 2012-09-20T04:08:19Z 2012-09-20T04:21:14Z <p>probably many thms and applications of math that dont explicitly refer to hypergraphs are actually related to them implicitly &amp; could be recast in those terms. because hypergraphs are equivalently just "sets of sets". in this way they're also often interchangeable with/analogous to a 2d boolean array in computer science (and how ubiquitous is <em>that</em> structure in both software and mathematics? in computer science it might be referred to as a "design pattern" or even just a simple "discrete structure").</p> <p>here is one key appearance/application of hypergraphs not mentioned so far. the erdos-rado sunflower lemmas[1], a key discovery of extremal graph/set theory, are about an intrinsic order or emergent "structure" to "random" hypergraphs if certain somewhat modest constraints are satisfied. this lemma shows up in numerous important lower bounds proofs in monotone circuit theory in computer science, including new versions that strengthen or generalize the lemma.[2]</p> <p>because of their particular role in these "bottleneck"-type proofs its not outlandish to conjecture that variations might be crucial in some future-established comp sci complexity class separations.</p> <p>[1] <a href="http://cstheory.stackexchange.com/questions/12641/detailed-materials-on-sunflowers" rel="nofollow">erdos-rado sunflowers survey/refs, TCS.se</a></p> <p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526" rel="nofollow">The Monotone Complexity of k-Clique on Random Graphs</a> by Rossman, containing new stronger lemmas on "quasi sunflowers"</p> <p>[3] <a href="http://gowers.files.wordpress.com/2009/05/razborov2.pdf" rel="nofollow">Razborovs method of approximations</a> by WT Gowers</p> http://mathoverflow.net/questions/107627/counting-intersecting-cliques-of-same-size counting intersecting cliques of same size vzn 2012-09-19T23:13:55Z 2012-09-19T23:13:55Z <p>(earlier tried to count the following but came up with a wrong formula so will just ask the direct question without proposing a formula 1st.)</p> <p>given: a graph of $m$ vertices, $\binom{m}{2}$ edges and a fixed clique of $\binom{n}{2}$ edges. </p> <blockquote> <ul> <li>how many other cliques on this graph are there of size $\binom{n}{2}$ edges that have at least one edge in common with the first fixed clique? (ie counting two cliques of same size on same graph, one fixed, the other variably-placed, with intersecting/shared edges, not disjoint.)</li> <li>prefer an end formula without binomial coefficient expressions in it. an asymptotic estimate may be ok.</li> <li>has someone seen this formula in a paper or book somewhere? esp interested in uses of it in comp sci refs/books/papers or extremal graph/set theory.</li> </ul> </blockquote> <p>(have a rough idea of how to count this but got messed up in the details.)</p> http://mathoverflow.net/questions/80228/compressing-graphs-kolmogorov-complexity-of-graphs/86338#86338 Answer by vzn for Compressing Graphs (Kolmogorov complexity of graphs) vzn 2012-01-21T22:40:20Z 2012-01-21T22:40:20Z <p>it depends on whether the graphs you want to compress have any particular repeated "structure" in the sense of something that can be recognized by an algorithm or if they are random (you dont specify-- suggest you edit question or specify this in comments for better feedback). if the graphs are random, compression is not possible just as theory predicts that "most strings are random". </p> <p>"random" graphs here can be roughly defined as a graph such that half of all the possible edges are distributed randomly. sparse graphs can be "compressed" in the sense that if you store only the edges that are present thats an improvement over storing a list of all edges with '1' or '0' for edge present or absent). nobody so far has suggested the somewhat obvious strategy for dense graphs of storing the inverse and then compressing that.</p> <p>any possible existing data compression algorithm can be used on graphs by converting the graph into a string using some conversion algorithm (ie 1-1 mapping between strings and graphs) and various conversion algorithms vs. the graph structure would affect how much the graph can be compressed.</p> <p>the question is also very much related to the question, "what are different ways/data structures to store graphs, esp those that take into acct repeated structures in the graph".</p> http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Comment by vzn vzn 2013-05-01T19:13:21Z 2013-05-01T19:13:21Z it appears the FSM transducer for this problem may be unpublished. a Collatz FSM transducer, some more details, ruby code, &amp; two nearby refs are given on this blog page, the Shallit+Wilson ref already listed, and Sinyor. <a href="http://vzn1.wordpress.com/code/collatz-conjecture-experiments/" rel="nofollow">vzn1.wordpress.com/code/&hellip;</a> http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence/129195#129195 Comment by vzn vzn 2013-05-01T04:32:00Z 2013-05-01T04:32:00Z this is the $K$ from Kolmogorov complexity? think it should be defined http://mathoverflow.net/questions/125870/counting-k-cliques-not-also-k1-on-random-graphs Comment by vzn vzn 2013-04-12T18:06:53Z 2013-04-12T18:06:53Z @douglas are you saying a closed form formula is unlikely to exist, or hard to find, etc? http://mathoverflow.net/questions/125870/counting-k-cliques-not-also-k1-on-random-graphs Comment by vzn vzn 2013-03-29T16:58:39Z 2013-03-29T16:58:39Z @andrew thanks. yes from Erdos-Renyi theory, $\log(n)$ is the so-called &quot;critical point&quot; where existence of k-cliques switches from low (P&lt;0.5) to high (P&gt;0.5) probability, and am looking for the answer in exactly that region where P=0.5. should have mentioned that in the question. will edit http://mathoverflow.net/questions/27716/does-there-exist-a-comprehensive-compilation-of-erdoss-open-problems Comment by vzn vzn 2013-03-18T15:28:43Z 2013-03-18T15:28:43Z old usenet sci.math post jul 11 1992 by greg kuperberg archived by rusin: <a href="http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd" rel="nofollow">math.niu.edu/~rusin/known-math/93_back/prizes.erd</a> http://mathoverflow.net/questions/33046/arent-oracle-machines-unsound-concepts Comment by vzn vzn 2013-03-06T18:03:01Z 2013-03-06T18:03:01Z have always felt there might be some possible logical contradictions that can ensue from &quot;not careful use&quot; ala contradictions that were found in the foundations of calculus long ago. http://mathoverflow.net/questions/85570/composite-finite-state-machines Comment by vzn vzn 2013-03-06T17:59:36Z 2013-03-06T17:59:36Z see krohn-rhodes decomposition, it seems to be related to your question: en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory. also the questions do not sound undecidable to me... http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Comment by vzn vzn 2013-03-06T17:52:29Z 2013-03-06T17:52:29Z possibility of it being groundbreaking seems to have increased with maybe no related research in the area... (the two are tied/coupled hence the statement as above)... maybe the bar is low.. but, agreed that this culture definitely regards something about self-citation as controversial/frowned on, splitting the vote with currently 6pro and 6con.... guess I will have to scan piles of meta msgs if attempting to determine the difference between legitimate self-citation/bkg/motivation and &quot;advertising&quot;. strangely, though, dont really have any product to sell... http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Comment by vzn vzn 2013-03-05T18:41:08Z 2013-03-05T18:41:08Z so, it appears from meta-oriented comments the off-the-books culture/convention is at odds with the on-the-books policy [from experience, a not uncommon on stack exchanges]. think the statement of the question above is quite straightforward and the contested section falls under &quot;provide background and motivation&quot;. <a href="http://mathoverflow.net/howtoask#motivation" rel="nofollow">mathoverflow.net/howtoask#motivation</a> http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Comment by vzn vzn 2013-03-04T17:25:06Z 2013-03-04T17:25:06Z no &quot;advertising&quot; in the post. teasing maybe? what exactly is an &quot;advertisement&quot;? is this just a unspoken social taboo/stigma or is there actually anything about it in official site policy? (or would that be awkward policy?) really do just want to know the state of literature on the subj &amp; any experts knowledge of that. here is some more bkg in [cs chat](<a href="http://chat.stackexchange.com/transcript/2710/2013/3/2" rel="nofollow">chat.stackexchange.com/transcript/2710/2013/3/2</a>). hope to hear from anyone interested in collatz or interested in an apparently fundamentally new approach http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination Comment by vzn vzn 2013-03-03T20:41:11Z 2013-03-03T20:41:11Z the point is, is there a ref, in the literature, ie <code>reference-request</code>, which further explores properties of its construction etc. http://mathoverflow.net/questions/86391/what-is-this-small-3-element-quasigroup-what-is-it-used-for Comment by vzn vzn 2013-01-27T19:03:00Z 2013-01-27T19:03:00Z ps sorry not too familiar with group theory, re prior comment ref to quasigroups, can someone confirm it is it indeed at least a quasigroup? http://mathoverflow.net/questions/86391/what-is-this-small-3-element-quasigroup-what-is-it-used-for Comment by vzn vzn 2013-01-27T18:57:32Z 2013-01-27T18:57:32Z GP thx for the ref &amp; plz edit it however you think would work better, took a stab at it. imho your ref/comment prob constitutes a great answer, plz convert to answer if possible http://mathoverflow.net/questions/93135/small-configurations-in-random-hypergraphs Comment by vzn vzn 2012-12-24T19:53:12Z 2012-12-24T19:53:12Z the partitioning into subhypergraphs seems similar to the szemeredi regularity lemma <a href="http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> ... http://mathoverflow.net/questions/93135/small-configurations-in-random-hypergraphs Comment by vzn vzn 2012-10-23T21:13:42Z 2012-10-23T21:13:42Z ok that helps some but still not following; it seems if you want to know the density of $A$ then you would look at $A$, not $\Gamma$. or also that any random subgraph of $\Gamma$ will tend to have the same density as $\Gamma$. is there something special about how $A$ is selected?