most recent 30 from http://mathoverflow.net 2013-06-20T01:34:04Z http://mathoverflow.net/feeds/question/96576 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96576/equidecomposable-graphs-unimodality-and-asymptotics Gjergji Zaimi 2012-05-10T14:57:31Z 2012-05-12T00:49:21Z

<p>I will call two graphs $G$ and $H$, $r$-equidecomposable (in analogy with <a href="http://en.wikipedia.org/wiki/Hilbert%27s_third_problem" rel="nofollow">Hilbert's third problem</a>) if they can be written as unions of disjoint subgraphs $$G\cong \bigsqcup_{i=1}^r G_i\quad ,\quad H\cong \bigsqcup_{i=1}^r H_i$$ (disjoint here means they have no common edges), and $G_i\cong H_i $ for $1\le i \le r$. Let $\epsilon(G,H)$ be the smallest $r$ for which $G$ and $H$ are $r$-equidecomposable. Let $$f(n,m)=\max_{G,H\in V(n,m) } \epsilon(G,H) $$ where $V(n,m)$ is the collection of all graphs with $n$ vertices and $m$ edges.</p> <p>Is the sequence $f(n,m)$ unimodal for fixed $n$? Can one find asymptotics for values such as $f\left(n,\frac{n(n-1)}{4}\right)$ when $n$ is large?</p>

http://mathoverflow.net/questions/96576/equidecomposable-graphs-unimodality-and-asymptotics/96579#96579 Joseph O'Rourke 2012-05-10T15:31:42Z 2012-05-10T15:31:42Z

<p>Not an answer (cool question!), just an excuse to show a pair of 2-equidecomposable graphs, one planar, one not: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/PetersenGraph2.jpg" alt="Petersen Graph"><br /></p>

http://mathoverflow.net/questions/96576/equidecomposable-graphs-unimodality-and-asymptotics/96723#96723 Gerhard Paseman 2012-05-12T00:49:21Z 2012-05-12T00:49:21Z

<p>If Joseph is going to take this as an opportunity to show some nice and illustrative pictures, I am going to do similarly, but using words instead. Gjergji probably already knows what I am going to say, but others might find the remarks a useful stepping stone to the subject.</p> <p>My initial thought was using a star graph, which on m nodes has a degree sequence of (m-1) 1's and 1 entry of (m-1). Embedding this into n=2m nodes and choosing H to be a graph of m disconnected edges gives that n/2 is a lower bound for f(n,n/2) and n even, and an analogous bound for n odd. Gjergji hints at a better construction in the comments which asymptotically gives a lower bound of 2n/3 .</p> <p>It so happens that every graph on n nodes is r-decomposable into star graphs for some r less than n. A nice argument on degree sequences allows one to remove a star graph from each of G and H leaving at least one vertex in one of the graphs with no edges, and then a second star graph can be removed from each to guarantee that a vertex in the other graph has no edges. This allows us to look at the situation on n-1 nodes and gives an upper bound of 2n (which can be tightened to 2n-6 for n>3) for f(n,m) for any m.</p> <p>If there is a relation between decomposability for a pair of graphs and decomposability for their complements, I have not found it yet. However having min (m, floor(2n/3)) and 2n as upper and lower bounds on parts of f suggests to me that f is unimodal, that there are nice asymptotics and that for m between n and ((n choose 2) - n), the asymptotic value for f(n,m) will be Cn for some constant C less than 2, most likely C=1.</p> <p>Using star graphs for the pieces provides nice results. It might be good to consider decomposition into certain graph classes like paths or trees and see what asymptotics can be found using such restrictions.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.05.11</p>