mm-3799 === Subject: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Consider the following conjecture. Conjecture. Let G be a finite connected regular graph. Let every vertex of G be in a 4-cycle (that is a cycle with four edges). Then G is hamiltonian (that is G has an Hamilton cycle). Can you find a counterexample? Simone === Subject: Re: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Consider the following conjecture. > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > Can you find a counterexample? > Simone I strengthen the previous conjecture. Let us denote by N(i) the set of the neighbours of a vertex i. Conjecture. Let G be a finite connected regular graph. Let every vertex of G be in a 4-cycle. Suppose that for every two vertices of G, i and j, the cardinality of the intersection of N(i) and N(j) is different from 1. Then G is hamiltonian. === Subject: Re: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Consider the following conjecture. > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > Can you find a counterexample? I think I can find a minimal one on 11 vertices. It's the graph Q350 on page 153 of Read and Wilson's amazing Atlas of Graphs. For your convenience, the adjacency matrix of the graph is: G = 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 Incidentally, I have recently written a paper together with a friend about a somewhat similar class of graphs. If you wish, I can send you a copy. Felix. === Subject: Re: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > > Consider the following conjecture. > > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > > Can you find a counterexample? > I think I can find a minimal one on 11 vertices. It's the graph Q350 > on page 153 of Read and Wilson's amazing Atlas of Graphs. Sorry, I should have said a minimal 4-regular one on 11 vertices. Felix. === Subject: Re: Regular graphs having every vertex in a 4-cycle Epigone-thread: tenbrilspoy Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Simone Severini conjectures: Conjecture. Let G be a finite connected regular graph. Let every vertex of G be in a 4-cycle (that is a cycle with four edges). Then G is hamiltonian (that is G has an Hamilton cycle). Can you find a counterexample? Start with the Petersen graph P. At each node x of P, attach K_6 by deleting one edge of K_6 and replacing it with two edges to x. The resulting graph is regular of degere 5. Any Hamiltonian cycle induces a Hamiltonian cycle on P. === Subject: Re: Regular graphs having every vertex in a 4-cycle 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Simone Severini conjectures: > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > Can you find a counterexample? > Start with the Petersen graph P. > At each node x of P, attach K_6 by deleting one edge of K_6 and > replacing it with two edges to x. > The resulting graph is regular of degere 5. > Any Hamiltonian cycle induces a Hamiltonian cycle on P. Of course, your counterexample and mine (which used a similar replacement starting from a single edge and attaching K_4's) are not very highly connected. Here's a way to do it and get a 6-regular 3-connected non-Hamiltonian graph in which every edge (not just every vertex) belongs to a 4-cycle: Start with K4. Replace each edge xy by a gadget formed by removing two nonadjacent edges pq and rs from a K7, and connecting p-x-q and r-y-s. Any Hamiltonian tour corresponds to an Euler tour of K4... -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science === Subject: Re: Regular graphs having every vertex in a 4-cycle 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Here's a way to do it and get a 6-regular 3-connected non-Hamiltonian > graph in which every edge (not just every vertex) belongs to a 4-cycle: > Start with K4. Replace each edge xy by a gadget > formed by removing two nonadjacent edges pq and rs from a K7, > and connecting p-x-q and r-y-s. Any Hamiltonian tour corresponds to an > Euler tour of K4... That should be 2-connected, not 3-connected, obviously. Probably a similar construction, starting from a set of n vertices (here n=4) and connecting every k-tuple of them by an appropriate gadget (here k=2), will give a k-connected regular non-Hamiltonian graph with the same 4-cycle property. -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science === Subject: Re: Regular graphs having every vertex in a 4-cycle 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > Can you find a counterexample? Consider the 3-regular graph with ten vertices and the following edges: 0 1 0 2 0 4 1 3 1 5 2 6 2 8 3 7 3 9 4 6 6 8 4 8 5 7 7 9 5 9 -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science === Subject: Re: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) >> Conjecture. Let G be a finite connected regular graph. Let every >> vertex of G be in a 4-cycle (that is a cycle with four edges). Then G >> is hamiltonian (that is G has an Hamilton cycle). >> Can you find a counterexample? >Consider the 3-regular graph with ten vertices and the following edges: In your example, drawn at http://www.oswego.edu/~baloglou/math/bridge.html for everybody's convenience, 01 is a bridge*: I suspect that Simone may in fact have a theorem here, namely that *every bridgeless 3-regular graph each vertex of which belongs to a 4-cycle does have a Hamilton cycle*. *likewise, in Felix Goldberg's 11-vertex 4-regular example there is a very 'central' vertex, see http://www.oswego.edu/~baloglou/math/central.html; but you have already provided more involved 4-regular examples anyway. baloglouAToswego.edu === Subject: Re: Regular graphs having every vertex in a 4-cycle Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Conjecture. Let G be a finite connected regular graph. Let every > vertex of G be in a 4-cycle (that is a cycle with four edges). Then G > is hamiltonian (that is G has an Hamilton cycle). > Can you find a counterexample? >>Consider the 3-regular graph with ten vertices and the following edges: >In your example, drawn at http://www.oswego.edu/~baloglou/math/bridge.html >for everybody's convenience, 01 is a bridge*: I suspect that Simone may in >fact have a theorem here, namely that *every bridgeless 3-regular graph each >vertex of which belongs to a 4-cycle does have a Hamilton cycle*. >*likewise, in Felix Goldberg's 11-vertex 4-regular example there is a very >'central' vertex, see http://www.oswego.edu/~baloglou/math/central.html; >but you have already provided more involved 4-regular examples anyway. > baloglouAToswego.edu Here is a 3-regular 3-connected counterexample. Start with the Petersen graph, which is not hamiltonian. Replace each vertex by the following gadget O O O /| K_{2,3} / | changes to O O O / | | | | The resulting graph is 3-regular and every vertex is in a 4-cycle. It has no bridges. In fact, it is 3-connected. Any hamilton cycle of this graph descends to a hamilton cycle of Petersen, so there are none. Dave Wagner === Subject: Re: probabilistic approach to riemann hypothesis Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > I want to notify the forum of two papers on the riemann hypothesis: > http://maa.org/features/chaitin.html > 2) My brief note which discusses and extends Chaitin's idea to attempt > to prove the RH by using probablistic methods at > http://arXiv.org/abs/math.GM/0309148 > Enjoy! > Craig Your Lemma :The expected value of mu(N) for a random variable N (1,...n) with uniform distribution approaches zero as n --> infinite. Is false. Because mu(N) has no limit, It changes from -1 to 1 according the parity of the number of factors of N (Except when a factor is repeated, then mu(N) = 0) The SUM[k=1,n] mu(k)/k -->0 when k -->inf. Due to mu(k) can be 1 or -1 L. Rodriguez === Subject: Re: probabilistic approach to riemann hypothesis Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Your Lemma :The expected value of mu(N) for a random variable N > (1,...n) with uniform distribution approaches zero as n --> infinite. > Is false. > Because mu(N) has no limit, It changes from -1 to 1 according the > parity of the number of factors of N (Except when a factor is > repeated, then mu(N) = 0) I haven't read Craig Feinstein's paper, but your argument here is wrong. Craig's statement is equivalent to M(x) = o(x) where M(x) := sum over n <= x of mu(n). I think that's known to be true; certainly M(x) = O(x^(1/2+h)) for any h>0 if RH holds. He isn't making any claim about mu(n) having a limit. -- Gareth McCaughan .sig under construc === Subject: probability problem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Someone once told me that the solution to the following problem was known only for even N (or maybe it was only for odd N) The problem is to show that if X and Y are two discrete random variables defined on the same finite sample space of size N>1 then X+Y cannot have a uniform distribution. Is this true? Is no solution known for an arbitrary N? === Subject: Re: probability problem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) >Someone once told me that the solution to the following problem was >known only for even N (or maybe it was only for odd N) >The problem is to show that if X and Y are two discrete random variables defined >on the same finite sample space of size N>1 then X+Y cannot have >a uniform distribution. >Is this true? Is no solution known for an arbitrary N? Easy counterexample: X is constant, Y has a (discrete) uniform distribution. Perhaps you want the ranom variables non-constant, also that you want each member of the sample space to have equal probability. Second counterexample: sample space {0,1,...,N-1}, X(i)=anything, Y(i) = i - X(i). Maybe you want X and Y to be independent? Third counterexample: if N = N_1 N_2 is composite, consider the sample space {0,1,...,N_1-1} x {0,1,...,N_2-1}, let X(a,b) = a and Y(a,b) = N_1 b. Then X+Y is uniform on {0,1,...,N-1}. Perhaps you're thinking of the case where N is prime? Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: Re: Goldbach-Idea - probably dumb! Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > I remember reading in a book, I think Recreations in the Theory of > Numbers by Dover, about lucky numbers, which are derived using > something like the Sieve of Eratosthenes, but with a different rule to > strike out the numbers. The numbers surviving the sieve are lucky > and include some primes and some composites. If I remember correctly, > the book said that the lucky numbers have properties similar to the > primes as far as their distribution, twin lucky numbers, and also obey > a Goldbach-like Conjecture. > Yes, I remember lucky numbers too. IIRC, start with 2,3,4,5,6,7,8,9,10,... > then strike out every 2nd number after 2: 2,3,5,7,9,11,13,15,17,19,21,23,25 > then 3rd 3: 2,3,5,7, 11,13, 17,19, 23,25 > then 5th 5: 2,3,5,7, 11,13, 17, 23,25 > and so on. > So 19 is not lucky, but 25 is. A lot of material is given in the OEIS lucky numbers sequence A000959: http://www.research.att.com/projects/OEIS?Anum=A000959 starting: 1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87, Hugo Pfoertner === Subject: Re: Goldbach-Idea - probably dumb! Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Experimentally the Lucky Numbers obeys the Goldbach's Conjecture and the distribution of prime numbers, but indeed that sequence is more complex that the sequence of primes. It suggests that the Goldbach's phenomenon is fortuitous. A lucky statistical encounter. Note: The Beiler's book Recreations in the Theory of Numbers, have not reference to Lucky Numbers. by sieves Gardiner,Lazarus,Metropoli,Ulam Mathematics Magazine (31) - 1956 Refer.: Unsolved Problems in Number Theory R.K.Guy - 2nd Edition-Springer 1994 === Subject: Characterizing a class of functions Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Let -inftyR with property that the set, of values at their extreme-points, is infinite . It's possible to characterize/ identify/ the class M ? How ? Also , same question for class N of all functions f:[a,b]-->R which have an infinite number of (strict)-maximum points. === Subject: Re: Question about the Prime Number Theorem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Im not an expert on prime number number theory (as the next few sentences may well demonstrate), but I'm under the impression that n(x) > x/log(x) only initially, and that someone (perhaps Littlewood) proved that the sign changes infinitely many times, even though convergence holds. William S. Heck > The prime number theorem states that, if n(x) is the number of primes not > exceeding x, then n(x) is asymptotic to x/log(x). Actually n(x) is greater > than x/log(x) (even though, of course, the approximation gets better with > bigger x). I'd like to know: > 1) if this fact has been demonstrated, that is, can I safely say that > n(x)>x/log(x)? > 2) And is there a way to estimate the error (for this question, I suppose > the answer is no)? > 3) if the answer to question 2 is no, can I say at least that, for example, > if I know that n(x)-x/log(x)=10203 for x=60000, then n(x)-x/log(x) is minor > or equal than 10203 for any x>60000? === Subject: Re: Question about the Prime Number Theorem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Im not an expert on prime number number theory (as the next few sentences > may well demonstrate), but I'm under the impression that n(x) > x/log(x) > only initially, and that someone (perhaps Littlewood) proved that the sign > changes infinitely many times, even though convergence holds. > William S. Heck Always n(x) > x/log(x). Also n(x) > x/(log(x)-1) if x > 5392 What Littlewood proved was that Li(x)-n(x) changes sign infinitely many times. L.Rodriguez === Subject: Re: Question about the Prime Number Theorem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) > Im not an expert on prime number number theory (as the next few sentences > may well demonstrate), but I'm under the impression that n(x) > x/log(x) > only initially, and that someone (perhaps Littlewood) proved that the sign > changes infinitely many times, even though convergence holds. That's pi(x) and Li(x), not pi(x) and x/log x. -- Gareth McCaughan .sig under construc === Subject: Re: Question about the Prime Number Theorem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) >Im not an expert on prime number number theory (as the next few sentences >may well demonstrate), but I'm under the impression that n(x) > x/log(x) >only initially, and that someone (perhaps Littlewood) proved that the sign >changes infinitely many times, even though convergence holds. You're thinking of li(x), not x/log(x). Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: Re: Question about the Prime Number Theorem Originator: bergv@math.uiuc.edu (Maarten Bergvelt) The Ross-Schoenfeld estimates were largely superseded by P.Dusart in his Thesis:: Autour la fonction qui compte le nombre de nombres premieres Universit.8e de Limoges 1998: Pi(x) > x / (Log(x) - 1) x > 5393 Pi(x) < x / (Log(x) - 1.1) x > 60184 L. Rodriguez - Merida- Venezuela === Subject: Weighted matroid optimization Originator: bergv@math.uiuc.edu (Maarten Bergvelt) I have this problem which is an extension of the weighted matroid optimization problem (I think). I have a ground set which is partitioned into number of subsets. Considering each of these subsets as individual ground sets of a matroid, we have the corresponding independent sets for each of them. Each of these independent sets have weights associated with them. Now, taking maximum one independent set for each of the ground set, we have to construct a minimum weight basis of the original ground set. Following is an example of what I am trying to say: Let G={ab, bc, ac, ar, br, cr} be the original ground set (edges of a network of vertices a,b,c,r). Let G1={ab,bc}, G2={ac,ar}, G3={br,cr} are the partitions. E1={NULL[0], (ab)[1], (bc)[2], (ab,bc)[3]} is the collection of independent sets from G1. Numbers in sqr. braces indicate weight. Similarly, E2={NULL[0], (ac)[3], (ar)[4], (ac,ar)[7]}, E3={NULL[0], (br)[5], (cr)[6], (br,cr)[11]} The minimum wt. basis of G will be {(ab,bc)[3], (ar)[4]} by inspection. Is this a known problem? Does there exist an algorithm (greedy or non-) for solving this problem, given the partition of G and weights? -- Samik Raychaudhuri University of Wisconsin, Madison http://samik.freeshell.org/ === Subject: ,,Generalized polynomial approximation Originator: bergv@math.uiuc.edu (Maarten Bergvelt) == Let r_0=0 , r_k=(k+1)/2 , k=1,2,... , and P(n) be the set of all linear combinations of the powers x^{r_k}, k=0,1,...,n, having real coefficients.Observe that Sum_{k=1 to infty}1/r_k = infty . According to a theorem proved in 1914 by Ch.H.Muntz , any continuous function f:[0,1]-->R , (f in C[0,1]), admits uniform approximation by linear combinations of the powers x^{r_k},k=0,1,.... Suppose that Z(n)=||z_{k,n}||_{0=< k =< n , n=1,2,...} is a triangular matrix such that 0=z_{0,n} < z_{1,n} < ... < z_{n,n}=1 , n=1,2,... . I am interested to find a sequence of (discrete) linear positive operators A_n:C[0,1]--->P(n) , n=1,2,..., having following approximation properties (f in C[0,1], n=1,2,...): i) (A_nf)(x)=SUM_{k=0 to k=n}p_{n,k}(x)f(z_{k,n}) with p_{n,k}(x) in P(n) , p_{n,k}>= 0 on [0,1] , 0=< k =< n , ii) (A_nf)(0)=f(0) , (A_nf)(1)=f(1) , iii) (A_nh)(x) = h(x) for any linear function , and if g(x)= x^2 or g(x)=x*sqrt{x} , then lim_{n-->infty} (A_ng)(x)=g(x) uniformly on [0,1] , iv) If f is increasing (resp. convex ) on [0,1], then A_nf is also an increasing (resp.convex) function on [0,1] , v) If f is convex on [0,1], then f(x) =< (A_{n+1}f)(x) =< (A_nf)(x) , x in [0,1] . Therefore the question is to find the knots Z(n) as well as the ,, generalized polynomials p_{n,k}(x) , k=0,1,...,n, that is to give a constructive proof of Muntz theorem (in this particular case). Note: Properties i)- v) are similar with those satisfied by Bernstein operators B_n , where (B_nf)(x)= SUM_{k=0 to k=n}b_{n,k}(x)f(k/n) , b_{n,k}(x)=C(n,k)x^k *(1-x)^{n-k} , C(n,k)=n!/(k!(n-k)!) . Any comments or results are welcome . ==