text:
location:  Publications → journals → CMB
Abstract view

# Degree Kirchhoff Index of Bicyclic Graphs

Published:2016-10-11
Printed: Mar 2017
• Zikai Tang,
College of Mathematics and Computer Science , Hunan Normal University, Changsha, Hunan 410081, P. R. China
• Hanyuan Deng,
College of Mathematics and Computer Science , Hunan Normal University, Changsha, Hunan 410081, P. R. China
 Format: LaTeX MathJax PDF

## Abstract

Let $G$ be a connected graph with vertex set $V(G)$. The degree Kirchhoff index of $G$ is defined as $S'(G) =\sum_{\{u,v\}\subseteq V(G)}d(u)d(v)R(u,v)$, where $d(u)$ is the degree of vertex $u$, and $R(u, v)$ denotes the resistance distance between vertices $u$ and $v$. In this paper, we characterize the graphs having maximum and minimum degree Kirchhoff index among all $n$-vertex bicyclic graphs with exactly two cycles.
 Keywords: degree Kirchhoff index, resistance distance, bicyclic graph, extremal graph
 MSC Classifications: 05C12 - Distance in graphs 05C35 - Extremal problems [See also 90C35]

 top of page | contact us | privacy | site map |


text:
User talk:Dionyziz

Need Help

The article vanavsos is up for deletion. Can you please help in this regard. Second, I am having difficulty with Wikinfo:Classical definition of republic and am having trouble on Talk:Republic because they won't allow an external link. It was deleted off of Wikipedia, and I believe it needs to come back on. A serious mistake in deleting this article. Thanks for your time.WHEELER 18:30, 8 Mar 2005 (UTC)

Thanks for asking so nicely, but I don't see a point in helping you regarding Talk:Republic. Quoting from the talk page: "See, you are just jealous. Compare your article republic with my article, Wikinfo:Classical definition of republic [...]. You can't even begin to write an article like I can." Well, as far as I know, Wikipedia is not about one writting a better article than the other, rather than all of us contributing to it in order to achive the best result. So, you'd better try to help build a better wikipedia by contributing in articles, instead of arguing all the time about certain little things (like an external link), IMHO. Sorry if I'm being offensive, but that's what I think!... Good luck. dionyziz 20:01, Mar 8, 2005 (UTC)

Wikiversity

I saw your name on the Wikiversity participant's list, you may be very experienced in mathematics already, but I'm trying out instructing a Calculus course if you're interested, go to Wikiveristy, check out the mathematics department, pure mathematics, and in the course list is included Calculus. Fephisto 22:37, 9 July 2006 (UTC)

Macedonians vs. Macedonian Slavs

Dear Dionyziz, you claim that you would allow for Macedonians to call themselves as they like but that for the sake of clarity, they should call themselves Macedonian Slavs. Have you considered the following two possibilities: 1. The present article "Macedonian Slavs" could also be titled "Macedonians (nationality)" and all articles that contain the different applications of the term "Macedonians" would have modifiers such as "nation", "geographic" or "Ancient" to make distinction; 2. The term "Macedonian Slavs" is not clear on its own because of all the Slavic people living in the region who do not consider themselves as Macedonians and because the Slavic nature of its own is disputed. In addition, I would like to underline that research has shown that the use of the term "Macedonians" in international relations as well as on the web refers to "People X" in most of the cases whereas the term "Macedonian Slavs" is outdated as of 2001. For more information, consider the various sources displayed on the talk page for the appropriate article. Clarity is, therefore, an argument that needs to be reconsidered. Thank you for your attention. Ivica83 12:30, 18 Jun 2005 (UTC)

Hello Ivica83. I can see your point when you say that the article "Macedonian Slavs" could also be titled "Macedonians (nationality)" for clarity. This is an interesting PoV, and you are right to say that the term "Macedonians" usually refers to "People X" in most of the cases. However, at the poll, as you can see by my arguments I am simply voting against the will of several Wikipedia contributors for the article to be renamed to "Macedonians". The current article about Macedonians is a really nice article IMHO with more or less a NPOV and shouldn't be replaced by an article about Macedonians in terms of people X; instead, it should stay as-is to clearly show the propaganda by all sides regarding the Macedonian matter. Instead of the article being named Macedonian Slavs, it could as well be renamed to Macedonians (nationality); I am simply against it being renamed to Macedonians. I have now added a comment at the comments section making this clear. --dionyziz 15:39, 18 Jun 2005 (UTC).

POLL

There is a poll in the talk page of Macedonian Slavs article here:

http://en.wikipedia.org/wiki/Talk:Macedonian_Slavs#The_poll

Some people are lobbying for changing the article's name to Macedonian without any qualifier. As it seems, a number of these people come from the Macedonian/Macedonian Slav wikipedia project. It seemed only fair to attract the attention of people possibly from the other side of the story. I hope that this message is of interest to you, if not please accept my apologies. Dstork 02:35, 18 Jun 2005 (UTC)Newcomer 05:45, 22 Jun 2005 (UTC)

Wikipedians in Greece

Hi, I understand that you are either Greek Wikipedian or a Wikipedian living in/with an interest in Greece.

The category page Wikipedians/Greece has been replaced with Category:Wikipedians in Greece but your name still appears on the old list. You might considering moving it. You might also consider adding adding Template:Greekwiki to your user page.

A Wikipedia:Greek Wikipedians' notice board has been in existence for some time but is terribly underutilised. It would certainly benefit from your involvement.--Damac 12:14, 23 November 2005 (UTC)

Thanks :-) dionyziz 18:08, 23 November 2005 (UTC)

RE: WikiProject Anime and manga participantion

You are listed at a participant of WikiProject Anime and manga. A recent change in how participants are listed — using a category — will result in your inadvertent removal from the project. If you wish to continue your participantion, please check the the project page for details on how to add yourself back to the project. --TheFarix 00:26, 11 March 2006 (UTC)

Dijkstra and running time notation

Hello, I noticed your interesting edits on Dijkstra's algorithm. Please keep in mind that, in usual notation, V is a set of vertices and E is a set of edges; therefore, the O-notation cannot be written the way you are suggesting. For example, O( ${\displaystyle V^{2}}$ ) has no particular meaning since V is a set. We usually either define two variables, m and n, to measure the size of our graph:

m = |V| n = |E|

However, it is sometimes handy to present asymptotic running-time notation in terms of h(|V|, |E|)-type functions. For example, the running time for Dijkstra using Fibonacci heaps would be O(|E| + |V|lg|V|). I have modified the article using this notation.

--dionyziz 12:26, 15 March 2006 (UTC).

I used as a reference "Introduction to Algorithms, Second Edition", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press 1. I understand what you say, and it's an interesting observation. But in the Analysis of the algorithm, and I quote

If the graph is sufficently sparse-in particular, ${\displaystyle E=o(V^{2}/log(V))}$-it is practical to implement the min-prioriry queue with a binary min-heap.

And it goes on, using this as standard notation for all algorithms. Now my doubt is: is it just a matter of syntax, agree on common notation, or is it that the idea behind has some little differences? Federico Pistono 17:49, 15 March 2006 (UTC)
"Introdocution to Algorithms, Second Edition", please refer to page 526:
"In describing the running time of a graph algorithm on a given graph G = (V, E), we usually measure the size of the input in terms of the number of vertices |V| and the number of edges |E| of the graph. That is, there are two relevant parameteres describing the size of the input, not just one. We adopt a common notational convention for these parameters. Inside asymptotic notation (such as O-notation or Θ-notation), and only inside such notation, the symbol V denotes |V| and the symbol E denotes |E|. For example, we might say, "the algorithm runs in time O(VE)," meaning that the algorithm runs in time O(|V||E|). This convention makes the running-time formulas easier to read, witrhout risk of ambiguity."
The question is: Should we adopt this convention in Wikipedia? I believe yes, but if we do, we should mention it somewhere. --dionyziz 09:13, 16 March 2006 (UTC).
I see. I had the feeling that I had read that part some time ago, but I did not manage to find it in ${\displaystyle O(1)}$ time ( ^_^ ), therefore eventually I gave up. I think we should insert this specific in the main article of the O notation, and use it as a standard for all the relative articles, in order to create a simple and fluid understanding of the whole argument for the reader. Furthermore, it is necessary to have an handy link to the spec, something like further information about the O notation (indented) in each one of the article that use such a notation. Federico Pistono 12:59, 16 March 2006 (UTC)
Please see Big_O_notation#Graph_Theory --dionyziz 14:41, 16 March 2006 (UTC).

Vandalism?

Dionyziz, I'd like to debate your comment on reverting my changes to Template:User vb-4 ("vandalism by Sohum"). I would not think that this is vandalism, as many userboxes utilise humour, (e.g. Template:user maybe ET, Template:user AIM-able). If you suggest that programming languages should not have such frivolity, I would point you to Template:user sql-N. I was trying to add a little bit more humour to the pages of expert VB programmers. Sohum 06:06, 29 April 2006 (UTC)

banikas

i wrote a stub about banikas. if you know sthg more pls contribute--Greece666 06:47, 14 May 2006 (UTC)

Sorry, I don't. --dionyziz 21:01, 24 July 2006 (UTC)

Blogcube UBX

I added a Blogcube UBX to your user page. Just letting you know. --Anthony5429 01:30, 20 August 2006 (UTC)

Wonderful! Thanks :) --dionyziz 00:41, 22 August 2006 (UTC)

Hey hon

It's so great that you're a user of WP! JSIN 09:50, 16 October 2006 (UTC)

MA Userbox

Today, there was a merger of Category:Martial Artist Wikipedians into Category:Wikipedian martial artists. This resulted in a userbox {{User:TonyTheTiger/Userboxes/Martialartist}} being added to the category. This userbox is available to you. TonyTheTiger 20:14, 17 January 2007 (UTC)

Thanks =) dionyziz 22:58, 17 January 2007 (UTC)

Check these out

--77.49.2.14 19:29, 25 March 2007 (UTC)

Ninjutsu

I see you have now removed the schools section from the article to the bujinkan one which seems more appropriate as not all ninjutsu is related to the bujiukan hence my removal. The qualifier is still relevent as the source is from the bujinkan so it is their pov not a fact. Hope that clarifies the reason for my edits --Nate1481( t/c) 14:38, 30 January 2008 (UTC)

You have to much info about you!

Someone might rape you. —Preceding unsigned comment added by Moldy912 (talkcontribs) 01:15, 17 February 2008 (UTC) A hah! Very nice. I will definately be one of those people loving you and not raping you. —Preceding unsigned comment added by Moldy912 (talkcontribs) 01:21, 17 February 2008 (UTC)

Oh! are you saying I don't post constructive edits and that I should???

Because if you are, tis ok with me. Moldy912 (talk) 00:31, 18 February 2008 (UTC) Hah, I am talking about when you said that you hope to see me edit a page constructively. I was pretending to take that into offense. You don't work for wikipedia do you? You sound very formal. I am a normal guy, not your boss. Loosen up in your speech! Moldy912 (talk) 00:36, 18 February 2008 (UTC)

SWOT landscape

RE: SWOT-landscape: I think you misunderstood. This edit is from the Swedish Agency for Innovation Systems (VINNOVA) and shows a new method. VINNOVA is non-profit and governmental body Bests regards Tord Beding —Preceding unsigned comment added by 195.198.161.217 (talk) 01:00, 19 February 2008 (UTC)

In order to stimulate innovativeness VINNOVA makes this new visualization technology available. The costs of using this new method is a self-cost :i.e. no profit involved. VINNOVA could be seen as a non-profit third party organization. Please check:
http://www.vinnova.se/misc/menyer-och-funktioner/Global-meny/In-English/
Will you please let me make this information available?
Bests
Tord Beding —Preceding unsigned comment added by 195.198.161.217 (talk) 01:23, 19 February 2008 (UTC)

Orphaned non-free media (Image:Typical vb6 session.png)

Thanks for uploading Image:Typical vb6 session.png. The media description page currently specifies that it is non-free and may only be used on Wikipedia under a claim of fair use. However, it is currently orphaned, meaning that it is not used in any articles on Wikipedia. If the media was previously in an article, please go to the article and see why it was removed. You may add it back if you think that that will be useful. However, please note that media for which a replacement could be created are not acceptable for use on Wikipedia (see our policy for non-free media).

If you have uploaded other unlicensed media, please check whether they're used in any articles or not. You can find a list of 'image' pages you have edited by clicking on the "my contributions" link (it is located at the very top of any Wikipedia page when you are logged in), and then selecting "Image" from the dropdown box. Note that all non-free media not used in any articles will be deleted after seven days, as described on criteria for speedy deletion. Thank you. BJBot (talk) 12:02, 14 March 2008 (UTC)

Template:Dionyziz DeleteMe

Hello, this is a message from an automated bot. A tag has been placed on Template:Dionyziz DeleteMe, by another Wikipedia user, requesting that it be speedily deleted from Wikipedia. The tag claims that it should be speedily deleted because Template:Dionyziz DeleteMe is a test page.

To contest the tagging and request that administrators wait before possibly deleting Template:Dionyziz DeleteMe, please affix the template {{hangon}} to the page, and put a note on its talk page. If the article has already been deleted, see the advice and instructions at WP:WMD. Feel free to contact the bot operator if you have any questions about this or any problems with this bot, bearing in mind that this bot is only informing you of the nomination for speedy deletion; it does not perform any nominations or deletions itself. To see the user who deleted the page, click here CSDWarnBot (talk) 22:10, 1 October 2008 (UTC)

Content-free criticism of my edit

What, exactly, does “suspicious edits” mean? [1] Can you say what was wrong with my edit or not? Michael Z. 2008-11-01 15:57 z

Okay, Cheers. 225's edit to Patton tank looked like a good-faith addition to me—I only improved the wording. Regards. Michael Z. 2008-11-01 17:51 z

Unreferenced BLPs

Hello Dionyziz! Thank you for your contributions. I am a bot alerting you that 1 of the articles that you created is tagged as an Unreferenced Biography of a Living Person. The biographies of living persons policy requires that all personal or potentially controversial information be sourced. In addition, to insure verifiability, all biographies should be based on reliable sources. if you were to bring this article up to standards, it would greatly help us with the current 3,009 article backlog. Once the article is adequately referenced, please remove the {{unreferencedBLP}} tag. Here is the article:

1. Alex Frost -

Thanks!--DASHBot (talk) 21:24, 8 January 2010 (UTC)

Hi. When you recently edited Integer factorization, you added a link pointing to the disambiguation page Binary (check to confirm | fix with Dab solver). Such links are almost always unintended, since a disambiguation page is merely a list of "Did you mean..." article titles. Read the FAQ • Join us at the DPL WikiProject.

It's OK to remove this message. Also, to stop receiving these messages, follow these opt-out instructions. Thanks, DPL bot (talk) 19:33, 18 February 2012 (UTC)

Hi. When you recently edited Ancient Egyptian multiplication, you added a link pointing to the disambiguation page Binary (check to confirm | fix with Dab solver). Such links are almost always unintended, since a disambiguation page is merely a list of "Did you mean..." article titles. Read the FAQ • Join us at the DPL WikiProject.

It's OK to remove this message. Also, to stop receiving these messages, follow these opt-out instructions. Thanks, DPL bot (talk) 10:21, 6 March 2012 (UTC)

Proposed deletion of Dimitris Fotakis

The article Dimitris Fotakis has been proposed for deletion because it appears to have no references. Under Wikipedia policy, this newly created biography of a living person will be deleted unless it has at least one reference to a reliable source that directly supports material in the article.

If you created the article, please don't be offended. Instead, consider improving the article. For help on inserting references, see Referencing for beginners, or ask at the help desk. Once you have provided at least one reliable source, you may remove the {{prod blp}} tag. Please do not remove the tag unless the article is sourced. If you cannot provide such a source within ten days, the article may be deleted, but you can request that it be undeleted when you are ready to add one. -- Patchy1 `REF THIS BLP` 11:07, 5 March 2013 (UTC)

File permission problem with File:Dimitris Fotakis.jpg

Thanks for uploading File:Dimitris Fotakis.jpg, which you've attributed to http://www.softlab.ntua.gr/~fotakis/. I noticed that while you provided a valid copyright licensing tag, there is no proof that the creator of the file has agreed to release it under the given license.

If you created this media entirely yourself but have previously published it elsewhere (especially online), please either

• make a note permitting reuse under the CC-BY-SA or another acceptable free license (see this list) at the site of the original publication; or
• Send an email from an address associated with the original publication to permissions-en@wikimedia.org, stating your ownership of the material and your intention to publish it under a free license. You can find a sample permission letter here. If you take this step, add {{OTRS pending}} to the file description page to prevent premature deletion.

If you did not create it entirely yourself, please ask the person who created the file to take one of the two steps listed above, or if the owner of the file has already given their permission to you via email, please forward that email to permissions-en@wikimedia.org.

If you believe the media meets the criteria at Wikipedia:Non-free content, use a tag such as {{non-free fair use}} or one of the other tags listed at Wikipedia:File copyright tags#Fair use, and add a rationale justifying the file's use on the article or articles where it is included. See Wikipedia:File copyright tags for the full list of copyright tags that you can use.

If you have uploaded other files, consider checking that you have provided evidence that their copyright owners have agreed to license their works under the tags you supplied, too. You can find a list of files you have created in your upload log. Files lacking evidence of permission may be deleted one week after they have been tagged, as described on criteria for speedy deletion. You may wish to read the Wikipedia's image use policy. If you have any questions please ask them at the Media copyright questions page. Thank you. Dianna (talk) 03:30, 11 March 2013 (UTC)

Greek help needed

Hello Dionyziz, I'm contacting you because we need some Greek translators to help with the deployment of the new VisualEditor on el.wikipedia. There are help pages, user guides, and description pages that need translating, as well as the interface itself. The translating work is going on over on MediaWiki: Translation Central. I also need help with a personal message for the Greek Wikipedians. If you are able to help in any way, either reply here, or head over to TranslationCentral. Thanks for your time, PEarley (WMF) (talk) 18:29, 22 July 2013 (UTC)

Hi. I can help. What are the next steps? --dionyziz (talk) 15:45, 26 July 2013 (UTC).
Dionyziz, great to have you on board. Here are the priority pages, simply click "translate this page" at the top to get started:
1. the User Guide, Greek is 75% complete.
2. FAQ, Greek is 77% complete. Any progress you can make with these two will help el.wiki users get up to date on VE. It would be great to get them finished off. Let me know if you have any questions/issues. PEarley (WMF) (talk) 16:38, 26 July 2013 (UTC)

File:Symbole-jp.png listed for deletion

A file that you uploaded or altered, File:Symbole-jp.png, has been listed at Wikipedia:Files for deletion. Please see the discussion to see why it has been listed (you may have to search for the title of the image to find its entry). Feel free to add your opinion on the matter below the nomination. Thank you. Sfan00 IMG (talk) 21:34, 2 August 2013 (UTC)

Proposed deletion of Core.onion

The article Core.onion has been proposed for deletion because of the following concern:

Only false positives found in Gbooks. Not notable?

While all constructive contributions to Wikipedia are appreciated, content or articles may be deleted for any of several reasons.

You may prevent the proposed deletion by removing the `{{proposed deletion/dated}}` notice, but please explain why in your edit summary or on the article's talk page.

Please consider improving the article to address the issues raised. Removing `{{proposed deletion/dated}}` will stop the proposed deletion process, but other deletion processes exist. In particular, the speedy deletion process can result in deletion without discussion, and articles for deletion allows discussion to reach consensus for deletion. Ten Pound Hammer(What did I screw up now?) 18:21, 15 November 2013 (UTC)

Nomination of Core.onion for deletion

A discussion is taking place as to whether the article Core.onion is suitable for inclusion in Wikipedia according to Wikipedia's policies and guidelines or whether it should be deleted.

The article will be discussed at Wikipedia:Articles for deletion/Core.onion until a consensus is reached, and anyone is welcome to contribute to the discussion. The nomination will explain the policies and guidelines which are of concern. The discussion focuses on high-quality evidence and our policies and guidelines.

Users may edit the article during the discussion, including to improve the article to address concerns raised in the discussion. However, do not remove the article-for-deletion notice from the top of the article. Ten Pound Hammer(What did I screw up now?) 01:27, 16 November 2013 (UTC)

RfC: New helper policy

Hello member of Category:Wikipedians who use IRC! You are invited to join an ongoing discussion on Wikipedia talk:IRC/wikipedia-en-help aimed at defining a policy for prerequisites to being a helper in the "#wikipedia-en-help connect" channel in a section titled "New helper policy".

To prevent future mailings about IRC, you may remove your user page from Category:Wikipedians who use IRC.
Assistance is available upon request if you can't figure out where it is being added to your user page.
This message has been sent by MediaWiki message delivery (talk) 10:58, 27 April 2015 (UTC) on behalf of — `{{U|Technical 13}} (e • t • c)`

ArbCom elections are now open!

Hi,
You appear to be eligible to vote in the current Arbitration Committee election. The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to enact binding solutions for disputes between editors, primarily related to serious behavioural issues that the community has been unable to resolve. This includes the ability to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail. If you wish to participate, you are welcome to review the candidates' statements and submit your choices on the voting page. For the Election committee, MediaWiki message delivery (talk) 12:57, 23 November 2015 (UTC)

File:Symbole-jp.png listed for discussion

A file that you uploaded or altered, File:Symbole-jp.png, has been listed at Wikipedia:Files for discussion. Please see the discussion to see why it has been listed (you may have to search for the title of the image to find its entry). Feel free to add your opinion on the matter below the nomination. Thank you. Stefan2 (talk) 22:26, 8 March 2016 (UTC)

Hi. Thank you for your recent edits. Wikipedia appreciates your help. We noticed though that when you edited Hybrid cryptosystem, you added links pointing to the disambiguation pages TLS and RSA (check to confirm | fix with Dab solver). Such links are almost always unintended, since a disambiguation page is merely a list of "Did you mean..." article titles. Read the FAQ • Join us at the DPL WikiProject.

It's OK to remove this message. Also, to stop receiving these messages, follow these opt-out instructions. Thanks, DPL bot (talk) 10:23, 21 June 2016 (UTC)

File permission problem with File:Dionyziz-2009.jpg

Thanks for uploading File:Dionyziz-2009.jpg. I noticed that while you provided a valid copyright licensing tag, there is no proof that the creator of the file has agreed to release it under the given license.

If you are the copyright holder for this media entirely yourself but have previously published it elsewhere (especially online), please either

• make a note permitting reuse under the CC-BY-SA or another acceptable free license (see this list) at the site of the original publication; or
• Send an email from an address associated with the original publication to permissions-en@wikimedia.org, stating your ownership of the material and your intention to publish it under a free license. You can find a sample permission letter here. If you take this step, add {{OTRS pending}} to the file description page to prevent premature deletion.

If you did not create it entirely yourself, please ask the person who created the file to take one of the two steps listed above, or if the owner of the file has already given their permission to you via email, please forward that email to permissions-en@wikimedia.org.

If you believe the media meets the criteria at Wikipedia:Non-free content, use a tag such as {{non-free fair use}} or one of the other tags listed at Wikipedia:File copyright tags#Fair use, and add a rationale justifying the file's use on the article or articles where it is included. See Wikipedia:File copyright tags for the full list of copyright tags that you can use.

If you have uploaded other files, consider checking that you have provided evidence that their copyright owners have agreed to license their works under the tags you supplied, too. You can find a list of files you have created in your upload log. Files lacking evidence of permission may be deleted one week after they have been tagged, as described on criteria for speedy deletion. You may wish to read Wikipedia's image use policy. If you have any questions please ask them at the Media copyright questions page. Thank you. Kelly hi! 07:53, 19 July 2016 (UTC)

ArbCom Elections 2016: Voting now open!

 Hello, Dionyziz. Voting in the 2016 Arbitration Committee elections is open from Monday, 00:00, 21 November through Sunday, 23:59, 4 December to all unblocked users who have registered an account before Wednesday, 00:00, 28 October 2016 and have made at least 150 mainspace edits before Sunday, 00:00, 1 November 2016. The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail. If you wish to participate in the 2016 election, please review the candidates' statements and submit your choices on the voting page. Mdann52 (talk) 22:08, 21 November 2016 (UTC)

Contemporary pop punk listed at Redirects for discussion

An editor has asked for a discussion to address the redirect Contemporary pop punk. Since you had some involvement with the Contemporary pop punk redirect, you might want to participate in the redirect discussion if you have not already done so. Steel1943 (talk) 19:16, 20 January 2017 (UTC)

format: plain


text:
# A sequence containing all positive rational numbers.

Question: Consider the following sequence $\{a_n\}_{n=1}^{\infty}$ defined as $a_1=1$ and for $n\ge1$ $a_{2n}=a_{n}+1$ and $a_{2n+1}=\dfrac{1}{a_{2n}}$. Show that the sequence has all positive rational numbers exactly once.

So far: In $a_n$ if $n$ is even $a_n>1$, and if $n>2$ is odd then $a_n<1$. If we can show that all positive rational numbers greater than $1$ are terms of the subsequence $a_{2n}$ we will be done. If $p/q$ is a positive rational in lowest form and $p>q$ then we have to show its a term of the subsequence. How can I do that?

Well I did prove the uniqueness of them, say $a_m=a_n$ and $m\neq n$ for the minimum $m+n$, its easy to see equality will hold if either both $m,n$ are even or both odd, from this we will get a contradiction to minimality assumption of $m,n$.

Please give some hints to proceed from here. If you have alternate solutions do share. What are some other sequences like this which cover the rationals/irrationals?

Thanks a lot!

• Hint: Look up "continued fractions" – Thomas Andrews Oct 15 '16 at 15:29
• Can we do it by induction on the the numerator and denominator? – gambler101 Oct 15 '16 at 17:54

You can do it by induction on the denominator.

I am going to write $f(m)=a_m$, because putting complicated formulae in subscripts is ugly.

First, show that $f(m)>1$ if and only if $m$ is even.

If your rational number is $\frac{p}{1}$ for some integer $p$, then $f(2^p)=p$.

Now, assume it is true for all rationals $\frac{p}{q}$ with $q<Q$. Let $P$ be another positive integer relatively prime to $Q$.

Applying the division algorithm, write $P=Qx+r$ where $x\geq 0$ and $0\leq r<Q$. If $r=0,$ then $Q$ divides $P$, which means they are not relatively prime of unless $Q=1$, which is already covered. So we can assume $0<r<Q$.

Now, by the induction hypothesis, we know that $\frac{Q}{r}=f(m)$ for some $m$, since $0<r<Q$. Since $\frac{Q}{r}>1$, we have that $m=2n$ for some $m$.

The last step, which I'll let you fill in, is to show that:

$$f(2^x(m+1))=\frac{P}{Q}$$

• Thanks I did induction on both numerator and denominator simultaneously. Anyways can you refer me some resources to learn continued fractions, sorry for off-topic question. – gambler101 Oct 17 '16 at 2:45

Hint: Indeed, use continued fractions and also the binary expansion of the index.

Take a positive rational number. Consider its continued fraction. Use pebbles (zeroes) for the partial quotients and reverse the fraction bars into ones. Reverse the sequence of zeroes and ones thus obtained and prepend a one. You got the binary expansion of the index of the term that equals that number

• I dont know continued fractions,can you give a reference for learning it. thanks for the reply. – gambler101 Oct 15 '16 at 17:53


text:
# American Institute of Mathematical Sciences

• Previous Article
Corrigendum to "On small data scattering of Hartree equations with short-range interaction" [Comm. Pure. Appl. Anal., 15 (2016), 1809-1823]
• CPAA Home
• This Issue
• Next Article
Dynamics of some stochastic chemostat models with multiplicative noise
September  2017, 16(5): 1915-1938. doi: 10.3934/cpaa.2017093

## Structure-preserving finite difference schemes for the Cahn-Hilliard equation with dynamic boundary conditions in the one-dimensional case

 1 Department of Mathematics, Kyoto University of Education, 1 Fujinomori, Fukakusa, Fushimi-ku, Kyoto, 612-8522, Japan 2 Division of Mathematical Sciences, Department of Integrated Science and Technology, Faculty of Science and Technology, Oita University, 700 Dannoharu, Oita, 870-1192, Japan 3 Department of Engineering for Production and Environment, Graduate School of Science and Engineering, Ehime University, Bunkyo-cho 3, Matsuyama, Ehime, 790-8577, Japan

* Corresponding author: yoshikawa@oita-u.ac.jp

Received  October 2016 Revised  April 2017 Published  May 2017

Fund Project: The authors are supported by JSPS KAKENHI Grant-in-Aid for Scientific Research(C), Grant Numbers 26400164 for TF and 16K05234 for SY

The structure-preserving finite difference schemes for the one dimensional Cahn-Hilliard equation with dynamic boundary conditions are studied. A dynamic boundary condition is a sort of transmission condition that includes the time derivative, namely, it is itself a time evolution equation. The Cahn-Hilliard equation with dynamic boundary conditions is well-treated from various viewpoints. The standard type consists of a dynamic boundary condition for the order parameter, and the Neumann boundary condition for the chemical potential. Recently, Goldstein-Miranville-Schimperna proposed a new type of dynamic boundary condition for the Cahn-Hilliard equation. In this article, numerical schemes for the problem with these two kinds of dynamic boundary conditions are introduced. In addition, a mathematical result on the existence of a solution for the scheme with an error estimate is also obtained for the former boundary condition.

Citation: Takeshi Fukao, Shuji Yoshikawa, Saori Wada. Structure-preserving finite difference schemes for the Cahn-Hilliard equation with dynamic boundary conditions in the one-dimensional case. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093
##### References:

show all references

##### References:
Relationship between $x$ and $k$
Discrete quantities $A_{1,d}^{(n)}$ and $M_d({{\mathit{\boldsymbol{U}}}^{\left( n \right)}})$
Discrete quantities $A_{2,d}^{(n)}$ and $M_{2,d}^{(n)}$
Case 1 for $\gamma =0.005$
Case 1 for $\gamma =0.001$
Case 1 for $\gamma =0.0005$
Case 2 for $\gamma =0.005$
Case 2 for $\gamma =0.001$
Case 2 for $\gamma =0.0005$
 [1] Laurence Cherfils, Madalina Petcu, Morgan Pierre. A numerical analysis of the Cahn-Hilliard equation with dynamic boundary conditions. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1511-1533. doi: 10.3934/dcds.2010.27.1511 [2] Georgia Karali, Yuko Nagase. On the existence of solution for a Cahn-Hilliard/Allen-Cahn equation. Discrete & Continuous Dynamical Systems - S, 2014, 7 (1) : 127-137. doi: 10.3934/dcdss.2014.7.127 [3] Alain Miranville, Sergey Zelik. The Cahn-Hilliard equation with singular potentials and dynamic boundary conditions. Discrete & Continuous Dynamical Systems - A, 2010, 28 (1) : 275-310. doi: 10.3934/dcds.2010.28.275 [4] Gianni Gilardi, A. Miranville, Giulio Schimperna. On the Cahn-Hilliard equation with irregular potentials and dynamic boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (3) : 881-912. doi: 10.3934/cpaa.2009.8.881 [5] Dimitra Antonopoulou, Georgia Karali. Existence of solution for a generalized stochastic Cahn-Hilliard equation on convex domains. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 31-55. doi: 10.3934/dcdsb.2011.16.31 [6] Sergey P. Degtyarev. On Fourier multipliers in function spaces with partial Hölder condition and their application to the linearized Cahn-Hilliard equation with dynamic boundary conditions. Evolution Equations & Control Theory, 2015, 4 (4) : 391-429. doi: 10.3934/eect.2015.4.391 [7] Changchun Liu, Hui Tang. Existence of periodic solution for a Cahn-Hilliard/Allen-Cahn equation in two space dimensions. Evolution Equations & Control Theory, 2017, 6 (2) : 219-237. doi: 10.3934/eect.2017012 [8] Jaemin Shin, Yongho Choi, Junseok Kim. An unconditionally stable numerical method for the viscous Cahn--Hilliard equation. Discrete & Continuous Dynamical Systems - B, 2014, 19 (6) : 1737-1747. doi: 10.3934/dcdsb.2014.19.1737 [9] Fausto Cavalli, Giovanni Naldi. A Wasserstein approach to the numerical solution of the one-dimensional Cahn-Hilliard equation. Kinetic & Related Models, 2010, 3 (1) : 123-142. doi: 10.3934/krm.2010.3.123 [10] Cecilia Cavaterra, Maurizio Grasselli, Hao Wu. Non-isothermal viscous Cahn-Hilliard equation with inertial term and dynamic boundary conditions. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1855-1890. doi: 10.3934/cpaa.2014.13.1855 [11] Qi Hong, Jialing Wang, Yuezheng Gong. Second-order linear structure-preserving modified finite volume schemes for the regularized long wave equation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6445-6464. doi: 10.3934/dcdsb.2019146 [12] Ciprian G. Gal, Alain Miranville. Robust exponential attractors and convergence to equilibria for non-isothermal Cahn-Hilliard equations with dynamic boundary conditions. Discrete & Continuous Dynamical Systems - S, 2009, 2 (1) : 113-147. doi: 10.3934/dcdss.2009.2.113 [13] Ciprian G. Gal, Maurizio Grasselli. Singular limit of viscous Cahn-Hilliard equations with memory and dynamic boundary conditions. Discrete & Continuous Dynamical Systems - B, 2013, 18 (6) : 1581-1610. doi: 10.3934/dcdsb.2013.18.1581 [14] Alain Miranville. Existence of solutions for Cahn-Hilliard type equations. Conference Publications, 2003, 2003 (Special) : 630-637. doi: 10.3934/proc.2003.2003.630 [15] Jie Shen, Xiaofeng Yang. Numerical approximations of Allen-Cahn and Cahn-Hilliard equations. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1669-1691. doi: 10.3934/dcds.2010.28.1669 [16] Desheng Li, Xuewei Ju. On dynamical behavior of viscous Cahn-Hilliard equation. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2207-2221. doi: 10.3934/dcds.2012.32.2207 [17] Laurence Cherfils, Alain Miranville, Sergey Zelik. On a generalized Cahn-Hilliard equation with biological applications. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 2013-2026. doi: 10.3934/dcdsb.2014.19.2013 [18] Álvaro Hernández, Michał Kowalczyk. Rotationally symmetric solutions to the Cahn-Hilliard equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (2) : 801-827. doi: 10.3934/dcds.2017033 [19] Xinlong Feng, Yinnian He. On uniform in time $H^2$-regularity of the solution for the 2D Cahn-Hilliard equation. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5387-5400. doi: 10.3934/dcds.2016037 [20] Ciprian G. Gal, Hao Wu. Asymptotic behavior of a Cahn-Hilliard equation with Wentzell boundary conditions and mass conservation. Discrete & Continuous Dynamical Systems - A, 2008, 22 (4) : 1041-1063. doi: 10.3934/dcds.2008.22.1041

2018 Impact Factor: 0.925


text:
# zbMATH — the first resource for mathematics

Irreducible factors of a class of permutation polynomials. (English) Zbl 07174374
The authors present results on the degrees of the irreducible factors of a permutation polynomial of the finite field $${\mathbb F}_q$$ of $$q$$ elements.
More precisely, they study permutation polynomials $$f_n(x)$$ recursively defined by $f_0(x)=ax+a_0,\quad f_i(x)=f_{i-1}^{d_i}(x)+a_i,~i=1,\ldots,n,$ where $$a\in {\mathbb F}_q^*$$, $$a_0,\ldots,a_n\in {\mathbb F}_q$$ and $$d_1,\ldots,d_n\ge 2$$ with $$\gcd(d_i,q-1)=1$$, $$i=1,\ldots,n$$. Note that each permutation polynomial is of this form with $$d_i=q-2$$, $$i=1,\ldots,n$$, and some $$n$$ by a well-known result of L. Carlitz [Proc. Am. Math. Soc. 11, 456–459 (1960; Zbl 0095.03003)].
The first main result (Theorem 2.2) is the following. Let $$d=\mathrm{lcm}(d_1,\ldots,d_n)$$ and assume $$\gcd(d,q)=1$$. Then the degree of each irreducible factor $$Q(x)$$ of $$F_n(x)$$ is a divisor of $$d_1 d_2 \cdots d_{n-1}\mathrm{ord}_d(q)$$.
Moreover, (Theorem 2.3) the degree of $$Q(x)$$ is either $$1$$ or divisible by ord$$_\ell(q)$$ for some prime divisor $$\ell$$ of $$d$$. Several additional results are proved.
The results of this paper enable one to produce families of permutation polynomials of large degrees, where possible degrees of their irreducible factors are known. See also the follow-up paper of the same authors [ “ Permutation polynomials and factorization”, Cryptogr. Commun. 12, No. 5, 913–934 (2020; doi:10.1007/s12095-020-00446-y)], in particular, in view of applications.
##### MSC:
 11T06 Polynomials over finite fields 11T55 Arithmetic theory of polynomial rings over finite fields 12E20 Finite fields (field-theoretic aspects)
Full Text:
##### References:
 [1] Anbar, N.; Odzak, A.; Patel, V.; Quoos, L.; Somoza, A.; Topuzoğlu, A., On the Carlitz rank of permutation polynomials: recent developments, (Bouw, I.; Ozman, E.; Johnson-Leung, J.; Newton, R., Women in Numbers Europe II, Contributions to Number Theory and Arithmetic Geometry. Women in Numbers Europe II, Contributions to Number Theory and Arithmetic Geometry, Association for Women in Mathematics Series, vol. 11 (2018), Springer) · Zbl 1445.11140 [2] Carlitz, L., Permutations in a finite field, Proc. Am. Math. Soc., 4, 538 (1953) · Zbl 0052.03704 [3] Gómez-Pérez, D.; Ostafe, A.; Sha, M., The arithmetic of consecutive polynomial sequences over finite fields, Finite Fields Appl., 50, 35-65 (2018) · Zbl 1400.11154 [4] Hou, X., Permutation polynomials over finite fields - a survey of recent advances, Finite Fields Appl., 32, 82-119 (2015) · Zbl 1325.11128 [5] Kalaycı, T., On factorization of some permutation polynomials over finite fields (January 2019), Sabancı University: Sabancı University İstanbul, Turkey, PhD thesis [6] Mullen, G. L.; Panario, D., Handbook of Finite Fields (2013), Chapman and Hall: Chapman and Hall London · Zbl 1319.11001 [7] Topuzoğlu, A., Carlitz rank of permutations of finite fields: a survey, J. Symb. Comput., 64, 53-66 (2014) · Zbl 1332.11106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Viewpoint: Photoreceptors Measure Photon Statistics

, Moscow State University, Faculty of Physics, Department of Quantum Electronics, Moscow, 119991, Russia
Published September 10, 2012  |  Physics 5, 103 (2012)  |  DOI: 10.1103/Physics.5.103

#### Measurement of Photon Statistics with Live Photoreceptor Cells

Nigel Sim, Mei Fun Cheng, Dmitri Bessarab, C. Michael Jones, and Leonid A. Krivitsky

Published September 10, 2012 | PDF (free)

For many years, people have tried to understand the structure of vision and its role in the perception of the world by living organisms. Suffice it to say that, thanks to their visual organs, people receive most of their information about the world by optical means. Eyes of living organisms represent advanced light harvesting systems, developed through hundreds of millions of years of evolution. Some of their features are comparable or even superior to existing man-made photodetection devices. For example, rod photoreceptor cells of the retina, which are responsible for night vision, are small photodetectors, containing a photosensitive element (rhodopsin pigment) along with a “built-in” chemical power supply (adenosine triphosphate produced by mitochondria). Remarkably, these photodetectors have very high sensitivity, down to the single-photon level.

As a result of this high sensitivity, statistical features of the photon fluxes (or, in other words, probability distribution of numbers of photons in each detection event) generated by different light sources might be monitored by these natural biological photodetectors. A crucial step towards a deep understanding of photoreceptor functioning would be a careful characterization of their response to well-controlled classical light sources. Such a study forms the focus of the work reported in Physical Review Letters by Nigel Sim and colleagues at the Data Storage Institute in Singapore [1], and it can be considered a pioneering research effort performed at the interface between physics and biology.

Many worthy experiments related to the sensitivity of the isolated rods have been performed in the past. However, either the statistics of rod response was not of interest to those researchers, or the noise properties of individual rods were difficult to assess since several hundred rods were simultaneously illuminated, so their collective response undergoes several intermediate stages of visual processing.

The objects under study are vertebrate retinal photoreceptor rod cells, which are densely packed in the retina in a layer covering the inner surface of an eyeball. Individual rods consist of two distinctive functional regions: an extended rodlike outer segment, which is filled with rhodopsin photopigment molecules, and a shorter, rounded, inner segment containing various components of cell machinery (Fig. 1, top). In the dark, the electrochemical gradient across the rod cell membrane causes a continuous ion flux in and out of the cell through aqueous pores in the membrane. Photons, impinging on the outer segment, cause reconfiguration of a rhodopsin molecule, which initiates a series of intracellular reactions. A fraction of the ion channels close, resulting in a sort of polarization of the cell and excitation of a signal to the optic nerve. Illumination with a relatively bright flash closes all light sensitive channels in the outer segment and bleaches the rod. A recovery process regulates reopening of the ion channels to the resting state.

The current experiments were performed with a so-called suction-electrode technique [2]. In this case, the outer segment of the rod is drawn into a tight-fitting glass microelectrode filled with a solution that reproduces physiological conditions. The ion current through the membrane is redirected to a low-noise amplifier and then is properly detected. It is important to stress that the tested rod works in a way similar to the in vivo system. Of course, this technique and the experiments described in the work [1] do not answer the question about the role of the brain in processing information collected by the biological receptor. However, Sim et al. obtained a clear answer to the question of the fundamental possibility of distinguishing between different types of light statistics by such detectors.

The technique described above allows the authors to study the influence of controllable photon fluctuations on the response of an isolated rod in the whole dynamic range of its response. To create the stimulus, they used two types of light sources with different statistics (a coherent laser beam and a “pseudothermal” source obtained by sending the same laser beam through a rotating ground-glass disk). Indeed, the coherent statistics serve, in some sense, as a reference because the average number of photons coincides with its variance, while the photon distribution with thermal statistics tends to bunching, which gives rise to “excess” correlations. The experimental results revealed a crucial influence of the bleaching of the rod on the fluctuations of its response.

In the experiments, the light beam coming from the selected source was sent into a standard Hanbury Brown and Twiss interferometer (this interferometer consists of a $50/50$ beamsplitter that equally distributes the initial beam between two output arms) coupled with a pair of fibers. One of the fibers is connected to a regular avalanche photodiode detector and the other stimulates the rod. With this setup, Sim et al. were able to obtain intensity correlations for the different light sources from the joint measurement of the rod and a reference detector. The retinas were taken from the dark-adapted eyes of adult male frogs (Xenopus laevis) and sliced with a blade to release single rods. The rods were loaded into a solution-filled chamber in a microscope, and a glass micropipette was used for conventional suction-electrode recordings. The outer segments of intact rods were captured in the pipette by gentle air suction (Fig. 1, bottom). The photocurrent pulses were amplified, digitized, and analyzed by computer.

Sim et al. analyzed their data, and under some reasonable assumptions, found good agreement between theory and experiment. In particular, each photon isomerizes only a single rhodopsin molecule and in the absence of saturation, subsequent electrophysiological responses to individual isomerizations are additive and have a standard Gaussian shape.

The research performed by Sim et al. [1] reveals how the normalized average photocurrent amplitudes and the second-order intensity correlation function depend on the average numbers of photons for coherent and pseudothermal sources. These dependences demonstrate that saturation of the photocurrent amplitude for the coherent source is significantly steeper than for the pseudothermal one. This can be explained by the influence of the excess correlations inherent in the thermal statistics (in comparison with the coherent one) on the response of the individual rods. Thus correlations of the pseudothermal source are gradually neglected due to the saturation of the rod response. Indeed, for the pseudothermal source, unlike the coherent source, the probability of occurrence of a relatively low number of photons remains non-negligible, even for a large value of the average. This results in the widening of the amplitude probability distribution and prevents sharp saturation of the response. Moreover, at a relatively low number of impinging photons, the statistics of the response is not affected by the saturation for both cases. However, when the rod is stimulated by bright flashes, the probability of the saturation amplitude becomes dominant and causes damping of the amplitude fluctuations. For the rods studied in the experiments, the typical number of photons per light pulse, which causes the saturation, was about one thousand.

With their results, the authors have shown that these biological receptors act, in some sense, like commercially available photodetectors used for quantum optics and quantum communication because they are able to distinguish between light sources with different statistical properties. In spite of the fact that only classical light sources have been tested, these experiments clearly demonstrate the ability of receptors to respond to the photon statistics, and thus testing sources of quantum states of light would be the next logical step. Another important direction would be clarifying the role of the brain in processing the data coming from such receptors.

The work of Sim et al. [1] serves as a starting point for further investigation of biological sensors illuminated by nonclassical light fields. The results of such research could be motivation for building a whole family of advanced devices based on rod photoreceptors as well as fostering wider use of physical methods (including those used in quantum information/communication) in the study of biological structures.

### References

1. N. Sim, M. F. Cheng, D. Bessarab, C. M. Jones, and L. A. Krivitsky, ”Measurement of Photon Statistics with Live Photoreceptor Cells,” Phys. Rev. Lett. 109, 113601 (2012).
2. D. A. Baylor, T. D. Lamb, and K.-W. Yau, “The Membrane Current of Single Rod Outer Segments,” J. Physiol. 288, 589 (1979).

### About the Author: Sergey Kulik

Sergey Kulik graduated from Moscow State University (MSU) in 1986. He subsequently obtained his masters (1986), Ph.D. (1991), and habilitation degree (2001) at the Department of Quantum Radio-Physics (currently Department of Quantum Electronics). At present he is a full professor at the Faculty of Physics of MSU. He has published more then 90 papers in international scientific journals and organized several international workshops on quantum information science. His research interests cover experimental quantum optics and quantum information processing with multidimensional systems and application of entangled states to spectroscopy.


text:
# What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring.

Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.

My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!

• Perhaps Mixed or Colour-bounded Hypergraph Colouring might be a start? For instance, dx.doi.org/10.1016/j.disc.2008.04.019 Apr 27, 2013 at 23:53
• It seems your problem is in P, in two steps: (1) your problem is equivalent to finding a maximum-size subset of the edges such that every vertex has degree at most two, and (2) the latter problem seems to be in P by, say, reduction to matching. Regarding (1), note that any solution to your problem with k colors gives a degree-2 subgraph of size k (just retain one edge from each color), and conversely any degree-2 subgraph of size k gives a solution with k colors (just color each edge in the subgraph its own color, color the rest of the edges with any one of the colors). What am I missing? May 2, 2013 at 4:10
• I am sorry that there are several mistakes in your answer. At first, the problem "finding a maximum-size subset of the edges such that every vertex has degree at most two", is NP-hard, reduction to 3SAT(I do not really know how could it have reduction to matching). What's more, "any degree-2 subgraph of size k" does not give "a solution with k colors", for example, Complete Graph. Thank you all the same. May 2, 2013 at 6:33
• Yes, you're right. About (2), the step "color the rest of the edges with any one of the colors" can give some vertex edges of three colors. Separately, Marek Chrobak suggested the following algorithm to me. I think it gives a 3-approximation: (i) find a maximum matching M; (ii) color each edge in M its own unique color; (iii) color the remaining edges white. May 2, 2013 at 15:10
• @RIC_Eien: At the risk of further embarrassment.. Are you sure "the problem 'finding a maximum-size subset of the edges such that every vertex has degree at most two', is NP-hard"? Given G=(V,E), create bipartite G2=(U,W,E2), where for each vertex v in V there is v' in U and v'' in W, and E2={(u',w'') : (u,w) in E}. Then the matchings in G2 correspond to the degree-2 sets of edges in G, and the correspondence preserves size? (As each k-cycle C in G corresponds in G2 to either a 2k-cycle (if k odd) or two k-cycles (if k even).) So max-matching in G2 solves it. What am I missing this time? May 2, 2013 at 15:25

This problem is NP-hard and APX-hard; see: Adamaszek and Popa, Approximation and Hardness Results for the Maximum Edge $q$-coloring Problem, Lecture Notes in Computer Science 6507 (2010) 132-143.


text:
Tidal Disruption of Galaxies in Binary Systems
Session 7 -- Clusters of Galaxies/Binary Galaxies
Display presentation, Monday, June 12, 1995, 9:20am - 6:30pm

## [7.07] Tidal Disruption of Galaxies in Binary Systems

J. D. Capriotti (University of Minnesota)

The effect that the presence of spherically symmetric, isothermal $(\rho \sim r^{-2})$ dark matter halos about members of binary galaxies has on the nature of tidal disruption in these systems is considered for galaxy pairs whose members possess dark matter halos extending anywhere from the edge of their visible disks out to a distance of $1$ Mpc. The frequency of tidal disruption in binary galaxy samples is then predicted and compared to that observed in these samples in an attempt to place constraints on the size of galactic dark matter halos.


text:
# Math Help - IVT

1. ## IVT

I need to show that the polynomial p(x) =x^3+2x+b, where b is any real number, has a real root by applying the Intermediate Value Theorem. Any ideas? I would greatly appreciate any help.

2. the function is continuous. lim (x-> -inf) p(x) = -inf
lim (x -> +inf) p(x) = +inf

therefore by the intermediate value thm the function hits all values between -inf and +inf, including zero

something like that i think

3. When you say inf, I assume you mean infimum? How does that help? I don't mean to sound unappreciative, I'm just not making the connection.

4. inf ... infinity

5. ahhh... I'm an idiot . Makes much more sense now. Thanks a lot for the help!


text:
# What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle.

The problem is to compute $2^{2^t} \pmod n$ for specified values of $t$ and $n$. Here $n$ is the product of two large primes, and $t$ is chosen to set the desired level of difficulty of the puzzle.

Note that the puzzle can be solved by performing $t$ successive squarings modulo $n$, beginning with the value $2$. That is, set

• $W(0) = 2$,
• $W(i+1) = W(i)^2 \pmod n \quad$ for $i\ge0$,

and compute $W(t)$. There is no known way to perform this computation more quickly without knowing the factorization of $n$.

In 1999 they predicted that we'd have 10 GHz processors by now. I realise that raw GHz is a dumb way to measure speed, but how fast are computers for this kind of "intrinsically sequential" computing?

I guess my questions are:

1) What is the state of the art for computation which can not be parallelised?

2) Has anyone claimed to make any progress with this challenge?

-

The theory is explained in the research paper that introduced the idea:

The paper is cited in Rivest's description of the time capsule.

As the security analysis in that paper explains, there is no known way to use parallelism (including, e.g., multi-core machines) to speed up the repeated squaring process to any significant degree. The only known way that parallelism helps is to provide a modest speedup for each individual squaring operation; a multi-core machine may be able to compute the modular squaring operation a bit faster than a single-core machine, but the overall speedup available in this fashion is limited. For example, here is a quote from the paper:

repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget. Since the speed of hardware available to individual consumers is within a small constant factor of what is available to large intelligence organizations, the difference in time to solution is reasonably controllable.

As far as I know, this remains an accurate description of the state of the art. I don't know of anyone who has claimed any progress on the puzzle.

-
For the complexity-theory-minded folks at home, 'intrinsically sequential' ~ P-complete. The intrinsic assumption is that there exist problems in P not in NC. This seems likely but it is yet unproven. –  pg1989 Aug 8 '13 at 6:30

Unless $2^t$ is the order of $2$ in the group $\mathbb Z_n$, in which case the solution is trivial.

Unless the factors of $n$ are known, in which case the Chinese remainder theorem can be used.

Unless $n$ (or its factors) has a special form, with only a few sparse bits being set (e.g. $n = 2^a + 2^b + 1$) and similar cases where $n$ has only a few alternations between $1$s and $0$s in its binary expansion, in which case there are possibly fast reduction methods.

The case where $n$ is a power of $2$ minus $1$ and $t = n-1$ is the Great Internet Mersenne Prime Search and it is where you would find the state of the art of "fast" specialized software.

Quantum computing? From en.wikipedia.org/wiki/Shor's_algorithm: "In 2012, the factorization of 15 was repeated.[7] Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer" .... "The runtime bottleneck of Shor's algorithm is quantum modular exponentiation" . Still slow, and still impractical for large numbers .....

I am not aware of any proof that the problem can't be solved for general values of $t$ and $n$, neither that dependent steps of repeated squaring is the only solution.

After all, using a normal basis, squaring can be replaced by circular shifts. Have a look at http://en.wikipedia.org/wiki/Normal_basis.

-
If that factors of $n$ are known, you don't even need the CRT. You have enough information to reduce $2^t ~ \text{mod} ~ \varphi{(n)}$ and efficiently solve the puzzle. –  Thomas Jan 10 '13 at 3:58
@Pierre, this is pretty much covered in Rivest's scientific paper that goes with this. (The chances that $2^t$ is the order of $2$ in the group is vanishingly small. Part of the whole point is that $n$ is chosen so that it is hard to factor, and its factors are not known. And so on.) –  D.W. Jan 10 '13 at 6:34