Wikipedia:Reference desk/Archives/Mathematics/2009 December 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 18

Non-isomorphic digraphs

Hi,

Im trying to enumerate all non-isomorphic digraphs where each vertex has an indegree and outdegree both equal 2. Even better if only the connected ones are counted. The sequence in [1] shows the number of all digraphs with degree 2, and http://www.research.att.com/~njas/sequences/A007108 shows the number of connected digraphs with degree 2, but they count the total number of graphs, and not just non-isomorphic ones.

Here are some things I tried: Polya's Enumeration Theorem: I think I have a clear understanding of how it works, but am unable to apply it to graphs of this kind. Tried to look at the adjacency matrices. It seems to me that the eigenvalues are different iff the corresponding graphs are non-isomorphic, but have no idea how to prove it.

Here are the first couple of terms, starting with number of those non-isomorphic digraphs of degree 3: 1, 2, 5, 18, 62

And here are the connected ones: 1, 2, 5, 18, 60

thanks for any hints! —Preceding unsigned comment added by 68.219.194.109 (talk) 07:12, 18 December 2009 (UTC)

My experience is that with Polya's Enumeration Theorem or Burnside's lemma (which is usually all you would use for counting non-ismorphic objects), the enumeration of all objects has to be pretty straight forward or least you have to understand it pretty well. In this case the enumeration of all the digraphs is given at the OEIS site as

$\sum _{k=0}^{n}\sum _{s=0}^{k}\sum _{j=0}^{n-k}{\frac {(-1)^{k+j-s}n!(n-k)!(2n-k-2j-s)!}{s!(k-s)!((n-k-j)!)^{2}j!2^{2n-2k-j}}}$

which is already pretty scary looking. To apply Burnside in this case you've got to generalize this formula to one which counts the number graphs that are invariant under a permutation of the vertices of any possible cycle decomposition. So off hand I'd say if you're looking for some kind of formula then you've got your work cut out for you. But if you're looking for some kind of formula for all n then it's probably going to be Burnside or nothing. The good news is that once you have all the non-isomorphic ones, the number that are connected can be found pretty easily with generating functions.--RDBury (talk) 16:57, 18 December 2009 (UTC)

Continuous or not?

Is the function $f:\mathbb {Q} \rightarrow \mathbb {R}$ with $f(x)={\begin{cases}1{\mbox{ if }}x\geq {\sqrt {2}}\\-1{\mbox{ if }}x<{\sqrt {2}}\end{cases}}$ continuous? --84.61.183.89 (talk) 09:51, 18 December 2009 (UTC)

The function f is continuous iff the inverse image, under f, of any open set in $\mathbb {R}$ is open in $\mathbb {Q}$. If U is an open set containing 1 but not −1, $f^{-1}(U)=\{x\in \mathbb {Q} :{\sqrt {2}}\leq x\}$, which is open in $\mathbb {Q}$. Likewise, if V is an open set containing −1 but not 1, $f^{-1}(V)=\{x\in \mathbb {Q} :x\leq {\sqrt {2}}\}$, which is open in $\mathbb {Q}$. From this, one may conclude that the inverse image of any open set in $\mathbb {R}$, under f, is open in $\mathbb {Q}$, establishing the continuity of f. The reason both $f^{-1}(U)$ and $f^{-1}(V)$ are open is hidden below; if you like, you may attempt to understand this independently, but if you give up, you may click the "show" button below.

(Click the "show" button at the right to see why $f^{-1}(U)$ and $f^{-1}(V)$ are open or the "hide" button to hide it.)

Note that $f^{-1}(U)=({\sqrt {2}},\infty )\cap \mathbb {Q}$ and $f^{-1}(V)=(-\infty ,{\sqrt {2}})\cap \mathbb {Q}$; by definition of the subspace topology, and the fact that ${\sqrt {2}}$ is not a rational number, both of these sets are open in $\mathbb {Q}$.

--PST 10:28, 18 December 2009 (UTC)

It may also help to note that $f:\mathbb {Q} \rightarrow \mathbb {R}$ may be written as $f(x)={\begin{cases}1{\mbox{ if }}x>{\sqrt {2}}\\-1{\mbox{ if }}x<{\sqrt {2}}\end{cases}}$. --PST 10:35, 18 December 2009 (UTC)

Since ${\sqrt {2}}$ is not rational (and therefore not in the domain of f), the above is true. --PST 10:35, 18 December 2009 (UTC)

This is just as easy to establish using the point-wise definition of continuity: the limit of the function at a given point x will be 1 if x>sqrt(2), and -1 if x<sqrt(2), since the function is constant near x. Since this agrees with f(x), the function is continuous. --COVIZAPIBETEFOKY (talk) 12:32, 18 December 2009 (UTC)

Yes, it's continuous. Pick any rational number and ask wheter it's continuous at that point. Pick an open interval about that number that is small enough that every rational in the interval is on the same side of √2. Then use the radius of that interval as the δ in the ε-δ definition of continuity. Michael Hardy (talk) 04:40, 19 December 2009 (UTC)