most recent 30 from http://mathoverflow.net 2013-05-25T17:05:24Z http://mathoverflow.net/feeds/question/94147 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94147/defining-fuzzy-properties-of-crisp-graphs Hans Stricker 2012-04-15T19:56:57Z 2012-04-16T05:25:01Z

<blockquote> <p>Is there a standard procedure to define fuzzy generalizations of typical graph properties?</p> </blockquote> <p>Consider the concept of a <em>fuzzy clique</em>. Define the <em>cliqueness</em> $c(G)$ of a graph $G$ as the ratio $\text{deg}(G)\ /\ (|V(G)|-1)$ between the mean degree of $G$ and the number of its vertices (minus one). </p> <p>Alternatively: $c(G) = 2\ |E|\ /\ (|V|^2 - |V|)$. </p> <p>That is, a graph deviates from being a "true" clique with the number of its missing possible edges. But shouldn't the missing edges been distributed as uniformly as possible among the vertices? Isn't <strong>3</strong> more of a (fuzzy) clique than <strong>2</strong> (which is more of a "true" clique plus an extra vertex), even though they have the same <em>cliqueness</em>?</p> <p><img src="http://epublius.de/mathoverflow/fuzzy4.png" alt="alt text"></p> <p>Should one try to capture this (felt) difference between <strong>2</strong> and <strong>3</strong>? E.g. by considering higher moments of the distribution of missing edges? </p> <blockquote> <p>Is this program (including higher moments) executed somewhere? And how is it to be generalized?</p> </blockquote>

http://mathoverflow.net/questions/94147/defining-fuzzy-properties-of-crisp-graphs/94148#94148 Felix Goldberg 2012-04-15T20:17:54Z 2012-04-15T21:37:29Z

<p>I think fractional graph theory fits the bill...</p> <p>Also, spectral extremal graph theory might be interesting. There is a new and excellent survey by Nikiforov:</p> <p><a href="http://arxiv.org/pdf/1107.1121.pdf" rel="nofollow">http://arxiv.org/pdf/1107.1121.pdf</a></p>

http://mathoverflow.net/questions/94147/defining-fuzzy-properties-of-crisp-graphs/94181#94181 Andrew D. King 2012-04-16T05:25:01Z 2012-04-16T05:25:01Z

<p>One way to argue that 2 has more cliqueness than 3 is to take whatever graph clustering algorithm you like, and ask whether or not the graph ends up as one cluster. Likely 2 will be split into two clusters, whereas 3 will be one cluster, but this depends on the algorithm.</p> <p>The issue is discussed in Chapter 2 of my master's thesis (http://www.sfu.ca/~adk7/papers/mscthesis.ps) but it's eight years old and probably not the best reference out there.</p>