User ken w. smith - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:15:56Z http://mathoverflow.net/feeds/user/11124 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108093/topics-for-an-undergraduate-expository-paper-in-number-theory/117377#117377 Answer by Ken W. Smith for Topics for an Undergraduate Expository Paper in Number Theory Ken W. Smith 2012-12-28T01:57:29Z 2012-12-28T01:57:29Z <p><a href="http://en.wikipedia.org/wiki/Arithmetic_functions" rel="nofollow">Arithmetic functions</a> -- there are some nice, very accessible results about arithmetic functions and some questions about these (notably the sum of divisors, $\sigma$) date back to the Greeks (perfect numbers, amicable pairs, etc.) There is also a nice algebra of arithmetic functions using the operation of convolution. Many basic number-theoretic ideas (RSA!) have arithmetic functions hiding in the background. </p> <p>Example of arithmetic functions include the Euler totient $\phi$-function, $\sigma(n)=$ sum of divisors of $n$, $\tau(n)=$ number of prime divisors of $n$ and the Moebius function $\mu$. </p> <p>I once had a small team of undergraduates (who had <em>no</em> higher mathematics in their backgrounds) create their own arithmetic functions and analyze questions about iterates of the functions. </p> http://mathoverflow.net/questions/117321/is-there-an-infinite-number-of-combinatorial-designs-with-r-lambda2/117328#117328 Answer by Ken W. Smith for Is there an infinite number of combinatorial designs with $r=\lambda^{2}$ Ken W. Smith 2012-12-27T14:43:01Z 2012-12-27T14:43:01Z <p>I will go ahead and put this as an (attempt at an) answer. Looking at the <a href="http://en.wikipedia.org/wiki/Bruck%E2%80%93Ryser%E2%80%93Chowla_theorem" rel="nofollow">Bruck-Ryser-Chowla theorem</a> for symmetric designs, it appears that as long as $\lambda$ is not congruent to 2 modulo 4 then the BRC is satisfied. Therefore there are an infinite number of parameters for putative symmetric designs with $r=k=\lambda^2$. Since no family of this type appears in the chapter on symmetric designs in the <a href="http://www.emba.uvm.edu/~jdinitz/hcd.html" rel="nofollow">CRC Handbook of Combinatorial Designs</a> then I suppose that in general it is an open question as to whether symmetric designs with these parameters exist. (They certainly exist for $\lambda = 2, 3, 4, 5$ but are ruled out by the BRC for $\lambda = 6.$)</p> <p>If a symmetric design with $r=\lambda^2$ exists then its residual design also has this property.</p> <p>The problem of general $(v,b,r,k,\lambda)$ designs is much broader and I don't have an answer to the more general original question. (I assume that in the definition of combinatorial design" we do not allow repeated blocks.)</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/105053#105053 Answer by Ken W. Smith for Instances where an existence result precedes the constructive version Ken W. Smith 2012-08-19T20:30:24Z 2012-08-19T20:30:24Z <p>As I understand it, Hilbert's original solution to Gordan's Problem was nonconstructive, proving that every algebraic variety over a field had a finite generating set. (His result is now generally cited as "Hilbert's Basis Theorem", that polynomial rings over Noetherian rings are Noetherian.)</p> <p>In modern day algebraic geometry, Hilbert's nonconstructive argument is replaced by a very constructive process in which one generates a Groebner Basis for the algebraic set.</p> http://mathoverflow.net/questions/92194/graphs-which-are-distance-regular-with-respect-to-a-vertex-but-not-distance-re Graphs which are "distance-regular" with respect to a vertex (but not distance-regular) Ken W. Smith 2012-03-25T19:30:19Z 2012-03-25T19:30:19Z <p>A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for <em>all</em> vertices $x$ of $\Gamma$ and for all vertices $y$ of distance $i$ from $x$, the number of vertices $z$ adjacent to $y$ and distance $i-1$ from $x$ is $c_i$; the number of vertices $z$ adjacent to $y$ for distance $i$ from $x$ is $a_i$ and the number of $z$ adjacent to $y$ of distance $i+1$ from $x$ is $b_i.$ (See the paragraph on intersection numbers in this <a href="http://en.wikipedia.org/wiki/Distance-regular_graph" rel="nofollow">Wikipedia article on DRGs</a>.)</p> <p>For example, the <a href="http://en.wikipedia.org/wiki/Petersen_graph" rel="nofollow">Petersen graph</a> is distance-regular of diameter 2. For the Petersen graph the intersection numbers are $b_0=3, b_1=2; a_1=0, a_2=2; c_1=1, c_2=1.$ </p> <p>Two recent research projects (one with undergraduates) have led me to some graphs that satisfy a weaker condition -- they satisfy the conditions above for <em>some</em>, but not all vertices $x$. These graphs are not distance regular but <em>look</em> distance regular with respect to a particular vertex, that is, the intersection numbers $c_i, a_i, b_i$ are well-defined for the distributions of vertices of distance $i$ from the special vertex $x.$</p> <p>For example, fix a particular vertex $x_0$ in the Petersen graph and consider the six vertices not adjacent to $x_0$. These vertices lie on a hexagon, a cycle of length six. Replace that hexagon by two triangles. This new graph is no longer distance regular, but the integers $b_0, ..., c_2$ still count distributions of vertices with respect to that special vertex $x_0.$</p> <p><strong>Question.</strong> Is there a theory of these "local" distance-regular graphs? Do they have a name? (I think "locally distance-regular" is taken? There are a variety of generalizations of distance-regular graphs; a google search reveals "almost-" and "pseudo-" but none of those generalizations seem to quite describe my need for a graph which has at least one vertex $x$ with intersection numbers.)</p> <p>These "local" distance-regular graphs are fairly common in the sense that one can deform almost any distance regular graph into one of these "local" distance-regular graphs in a manner similar to the way the Petersen graph was deformed, above.</p> <p>I can show that some of the properties of DRGs persist in these generalizations, for example, the minimal polynomial of the DRG divides the minimal polynomial of the deformed" not-quite-distance-regular graph and so the eigenvalues of the DRG are a subset of the eigenvalues of the not-quite DRG. In many cases these "not-quite" DRGs have few eigenvalues. </p> http://mathoverflow.net/questions/83720/reconstructing-graphs-with-vertices-of-degree-k-and-k-1 Reconstructing graphs with vertices of degree $k$ and $k-1$ Ken W. Smith 2011-12-17T16:36:24Z 2011-12-18T06:51:46Z <p>The Graph Reconstruction Conjecture claims that any simple graph with 3 or more vertices is reconstructible from its "deck" of vertex-deleted subgraphs. (A nice introduction to this problem is at <a href="http://en.wikipedia.org/wiki/Reconstruction_conjecture" rel="nofollow">this Wikipedia page</a>.)</p> <p>My general question: I would be interested in <em>any</em> recent progress on the conjecture. The sources in the Wikipedia article seem to be quite old. (I also have a copy of a <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190010306/abstract" rel="nofollow">Bondy and Hemminger survey</a> from 1977. A more recent article by Ramachandran <a href="http://www.akcejournal.org/contents/vol1no1/Vol_1no_1-6.pdf" rel="nofollow">(in pdf here)</a> is from 2004 but like many works on this conjecture, quickly detours into other reconstruction questions, edge reconstruction, etc.)</p> <p>A more specific question: since one can reconstruct the degree sequence of a graph then any regular graph can be reconstructed. But graphs with exactly two degrees, $k$ and $k-1$, seem to be quite hard to reconstruct. I would be <em>especially interested</em> in results related to graphs with exactly two degrees, $k$ and $k-1.$ </p> <p>Even more narrowly, can we reconstruct graphs in which all vertices have degree 2 or 3? (Apparently Kocay worked on that in the early 1980s, says Ramachandran.) Surely "small" graphs of degrees {2,3} are accessible to modern computers so there may now be a place for fertile exploration on this problem? </p> http://mathoverflow.net/questions/83455/cospectral-graphs/83480#83480 Answer by Ken W. Smith for cospectral graphs Ken W. Smith 2011-12-14T23:41:18Z 2011-12-14T23:41:18Z <p>Connected strongly regular graphs with parameters $(v,k,\lambda)$ have eigenvalue $k$ appearing once and two other eigenvalues with prescribed multiplicity. In general there are many non-isomorphic graphs for a fixed parameter. There are two graphs with parameters $(16,6,2)$ and 15 with parameters $(25,12,5)$. The number of non isomorphic graphs can grow dramatically....</p> <p>All strongly regular graphs with parameter $(v,k,\lambda)$ are regular (so the degree sequence is obvious) and are cospectral. Either the graph or its complement meets your bound on the number of edges.</p> <p>Andries Brouwer maintains a nice webpage on strongly regular graphs <a href="http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html" rel="nofollow">here.</a> (Check out the number of $(36,15,6)$ strongly regular graphs!)</p> http://mathoverflow.net/questions/29006/counterexamples-in-algebra/68287#68287 Answer by Ken W. Smith for Counterexamples in Algebra? Ken W. Smith 2011-06-20T13:56:24Z 2011-06-20T13:56:24Z <p>Desmond MacHale wrote an article, "Minimal Counterexamples in Group Theory", Mathematics Magazine, 54 (1981), no. 1, 23–28. I've found this paper useful in an introductory algebra class and I like the philosophy of the paper, "Is X true? No, probably not. So what is a smallest counterexample?" A variation on the group theory (and Irish!) tune of MacHales appears <a href="http://www.maths.tcd.ie/pub/ims/bull56/GiG5608.pdf" rel="nofollow">here</a>. A followup article is "Constructing a minimal counterexample in group theory" by Arnold Feldman, also in Mathematics Magazine (1985).</p> http://mathoverflow.net/questions/55524/status-of-the-hadamard-circulant-conjecture/64560#64560 Answer by Ken W. Smith for Status of the Hadamard Circulant conjecture Ken W. Smith 2011-05-11T02:43:50Z 2011-05-11T02:43:50Z <p>The paper by Craigen and Jedwab points out a very definite flaw in the main theorem by Hurley, Hurley &amp; Hurley, providing a counterexample to that theorem. So the conjecture is still open.</p> <p>The paper by Leung and Schmidt (<a href="http://www.springerlink.com/content/5r4157r8244p31qw/" rel="nofollow">here</a>) gives the latest information about possible counterexamples to the Circulant Hadamard conjecture.</p> <p>A <a href="http://www.ntu.edu.sg/home/bernhard/CW/CW.html" rel="nofollow">website</a> of Bernhard Schmidt lists smallest open cases based (I believe) on the work of the paper cited above. The smallest open cases are, of course, quite large.</p> http://mathoverflow.net/questions/13682/which-mathematical-ideas-have-done-most-to-change-history/61503#61503 Answer by Ken W. Smith for Which mathematical ideas have done most to change history? Ken W. Smith 2011-04-13T03:21:17Z 2011-04-13T03:21:17Z <p>Public key encryption is the basis for secure communication over the internet and thus the basis for our internet economy. (If my students buy a song using iTunes then they are using public key encryption. See the Wikipedia <a href="http://en.wikipedia.org/wiki/Secure_Sockets_Layer" rel="nofollow"> article on TSL and SSL protocols</a>.)</p> <p>A fundamental form of public key encryption (widely used now and the also the first example of public key encryption) is the RSA algorithm. It is based on Euler's theorem that $a^{\phi(n)}\equiv 1 \mod n$ for all $a$ relatively prime to $n$.</p> <p>Without Euler's theorem we would not have RSA; without RSA we would not have IDEA, SSL, TSL and our internet economy.</p> http://mathoverflow.net/questions/48434/names-of-finite-groups/48442#48442 Answer by Ken W. Smith for Names of finite groups Ken W. Smith 2010-12-06T13:47:12Z 2010-12-06T13:47:12Z <p>It is difficult to come up with a consistent notation for all groups of a certain order since their construction is somewhat chaotic. We might be able to describe all the groups of order $p^3$ or $p^4$ but what about all groups of order $p^6$? Or order $p^4q^2$?</p> <p>The software package GAP (http://www.gap-system.org/) has a catalogue of all groups of order up to 2000 or so and so I've sometimes referred to groups by their catalogue number, for example, SmallGroup(96, 33) refers to a particular group in that library. (As does SmallGroup(512, 1000000)!)</p> http://mathoverflow.net/questions/117321/is-there-an-infinite-number-of-combinatorial-designs-with-r-lambda2 Comment by Ken W. Smith Ken W. Smith 2012-12-27T14:46:28Z 2012-12-27T14:46:28Z @Felix: thanks! -- your more general question is probably VERY open! btw, even if a symmetric design does not exist (such as $(211,36,6)$), there is still a possibility that a design exists with the residual parameters. http://mathoverflow.net/questions/117321/is-there-an-infinite-number-of-combinatorial-designs-with-r-lambda2 Comment by Ken W. Smith Ken W. Smith 2012-12-27T14:12:12Z 2012-12-27T14:12:12Z If we restrict the question just to symmetric designs (so that $v=b$) then there are examples $(7,4,2), (25,9,3), (61,16,4),(121,25,5)$ described in the CRC Handbook of Combinatorial Designs [link text][1] (The list does not go far enough to examine $\lambda=6$.) If one removes a block from such a design one obtains a residual design in which $r$ is still equal to $\lambda^2.$ So there are certainly a number of examples. It would be interesting to know if there are any infinite families. [1]: <a href="http://www.emba.uvm.edu/~jdinitz/hcd.html" rel="nofollow">emba.uvm.edu/~jdinitz/hcd.html</a> http://mathoverflow.net/questions/105403/a-repeated-balls-in-bins-markovian-process Comment by Ken W. Smith Ken W. Smith 2012-08-25T12:44:53Z 2012-08-25T12:44:53Z What is the Markov chain matrix&quot; $P$? Is there a connection between $P$ and the adjacency matrix of the graph $G$? http://mathoverflow.net/questions/102230/almost-all-loops-have-a-trivial-automorphism-group-almost-all-groups-have-a-non Comment by Ken W. Smith Ken W. Smith 2012-07-14T15:55:02Z 2012-07-14T15:55:02Z Most semigroups seem to have trivial automorphism (at least that is the result of an enumeration of small semigroups -- see the thesis of Andreas Distler, available on the internet.) A similar question (automorphism groups of free monoids vs. free groups) is at <a href="http://math.stackexchange.com/questions/109600/" rel="nofollow">math.stackexchange.com/questions/109600</a>. Note that semigroups and monoids obey the associativite law and yet seem to be non-symmetric in the sense that many have nontrivial automorphism groups. http://mathoverflow.net/questions/92194/graphs-which-are-distance-regular-with-respect-to-a-vertex-but-not-distance-re Comment by Ken W. Smith Ken W. Smith 2012-03-26T14:33:27Z 2012-03-26T14:33:27Z A follow-up -- much of the theory I need seems to be collected in section 9.3 (Equitable Partitions) of <i>Algebraic Graph Theory</i> by Chris Godsil and Gordon Royle (of course!) -- which I own and is sitting on my desk! I thank you both and I apologize for not putting these ideas together.... http://mathoverflow.net/questions/92194/graphs-which-are-distance-regular-with-respect-to-a-vertex-but-not-distance-re Comment by Ken W. Smith Ken W. Smith 2012-03-26T12:38:17Z 2012-03-26T12:38:17Z Thanks to both of you! &quot;Equitable partition&quot; is the key idea I am after, I think. I'll go ahead and get the JCT(B) article through interlibrary loan. http://mathoverflow.net/questions/83720/reconstructing-graphs-with-vertices-of-degree-k-and-k-1/83774#83774 Comment by Ken W. Smith Ken W. Smith 2011-12-18T14:01:56Z 2011-12-18T14:01:56Z Thanks. (The reconstruction conjecture and edge ideals, Dalili, et. al. Discrete Mathematics (Elsevier) v. 308, no. 10 (2008-01-01) p. 2002-2010. ISSN: 0012-365X.) I found a pdf by searching on the title. http://mathoverflow.net/questions/83720/reconstructing-graphs-with-vertices-of-degree-k-and-k-1/83761#83761 Comment by Ken W. Smith Ken W. Smith 2011-12-18T13:35:07Z 2011-12-18T13:35:07Z Yes, I think a computer search on degrees 2 and 3 would be very useful. (What's the best way to do this? I think I have an old version of Nauty installed on my Mac but it has been a while since I used it -- sorry!) Graphs with degrees 2 &amp; 3 would be (roughly) identified by the vertices of degree 3. &quot;Smooth out&quot; the vertices of degree 2, replacing edge-vertex-edge by a single edge, and one has a cubic graph. Can we reconstruct that cubic graph? http://mathoverflow.net/questions/83720/reconstructing-graphs-with-vertices-of-degree-k-and-k-1/83722#83722 Comment by Ken W. Smith Ken W. Smith 2011-12-17T17:07:07Z 2011-12-17T17:07:07Z That's the survey article by Ramachandran from 2004. (I couldn't find any other relevant ones from this century.)