Geometry.Net - Theorems_And_Conjectures: Open Problems

My Favorite Open Problems
open problems in Discrete Math. Prizes. More online collections of open problemsin discrete math Dan Archdeacon's problems in topological graph theory;
http://www.math.princeton.edu/~matdevos/open/open.html
Open Problems In Combinatorics
Part of the Combinatorics Net.Category Science Math Combinatorics open problemsopen problems in Combinatorics. open problems of Paul Erdös, by Fan RK Chung; OpenProblems from the SIAM Activity Group Newsletter in Discrete Mathematics;
http://www.combinatorics.net/problems/

Extractions: Open Problems in Combinatorics Unsolved Combinatorial Problems by Zsolt Tuza Open Problems on Perfect Graphs , by Positivitiy Problems and Conjectures in Algebraic Combinatorics , by Richard Stanley Ten Problems in Combinatorics, Lecture given by Gian-Carlo Rota at the Conference on Combinatorics and Physics (CAP'98), held at the Los Alamos National Laboratory, August 10-12, 1998. To be announced. Problems in Signed, Gain, and Biased Graphs , compiled by Thomas Zaslavsky Some Problems in Matroid Theory , compiled by Thomas Zaslavsky Unsolved Problems in Graph Theory , compiled by Stephen C. Locke A problem on transitive permutation groups , by Peter J. Cameron A list of problems on permutation groups , by Peter J. Cameron Unsolved Mathematics Problems , compiled by Steven Finch. , by Fan R. K. Chung Open Problems from the SIAM Activity Group Newsletter in Discrete Mathematics Problems on the Enumeration of Matchings (ps file) , by James Propp
The Open Problems Project
The open problems Project. This is the beginning of a project 1 to record open problemsof interest to researchers in computational geometry and related fields.
http://cs.smith.edu/~orourke/TOPP/Welcome.html

Extractions: Next: Numerical List of All The Open Problems Project edited by Erik D. Demaine Joseph S. B. Mitchell Joseph O'Rourke This is the beginning of a project to record open problems of interest to researchers in computational geometry and related fields. It commenced with the publication of thirty problems in Computational Geometry Column 42 [ ] (see Problems 1-30 ), but has grown much beyond that. We encourage correspondence to improve the entries; please send email to TOPP@cs.smith.edu . If you would like to submit a new problem, please fill out this template Each problem is assigned a unique number for citation purposes. Problem numbers also indicate the order in which the problems were entered. Each problem is classified as belonging to one or more categories. The problems are also available as a single Postscript or PDF file. To begin navigating through the open problems, you may select from a category of interest below, or view a list of all problems sorted numerically
Open Problems In Visib. + Illumn.
open problems in the Combinatorics of Visibility and Illumination. I willpost notices of solutions to the open problems listed in the paper.
http://cs.smith.edu/~orourke/Open.html

Extractions: Last update to this page: I will post notices of solutions to the open problems listed in the paper. Please keep me apprised of progress! orourke@cs.smith.edu Illuminating Rectangles. I quoted a lower bound of n-1 and an upper bound of ~(4/3)n in the paper. Jorge Urrutia shows in his chapter, "Art gallery and illumination problems" (to appear in the North-Holland Handbook of Computational Geometry ) that the Hoffman-Kaufman-Kriegel [n/4] result on orthogonal art galleries with holes establishes immediately that n+1 lights suffice. So the lower and upper bounds are nearly identical now: [n-1,n+1]. Stage Illumination. Proven NP-complete, even with these restrictions: the floodlights are all affixed to just two points, and those points have the same x coordinate, or the same y coordinate. See: H. Ito, H. Uehara, M. Yokayama, "NP-completeness of stage illumination problem", Proc. Japan Conf. Discrete Comput. Geom. '98 , Tokyo, 1998, pp. 88-92. ito@tutics.tut.ac.jp
Open Problems
Originally from the Katsiveli 2000 open problems Session, now maintained by Sergiy Kolyada. PDF/PS.Category Science Math Differential Equations Dynamical Systemsopen problems in Dynamical Systems Ergodic Theory. Welcome! 9, Polygonal billiardssome open problems Submitted by Pascal Hubert and Serge Troubetzkoy.
http://www.math.iupui.edu/~mmisiure/open/
Survey Of Venn Diagrams Open Problems
In the Electronic Journal of Combinatorics.Category Science Math Combinatorics open problemsVenn Diagram References combinatorial facts, beautiful figures, n=3and beyond, some open problems. Venn Diagram Survey open problems.
http://sue.csc.uvic.ca/~cos/venn/VennOpenEJC.html
L-functions And Random Matrix Theory
Conjectures and open problems concerning Lfunctions, focussing on the areas in which there has been recent progress using results from Random Matrix Theory. Maintained at AIM.
http://www.aimath.org/WWN/lrmt/

Extractions: L-functions and Random Matrix Theory This web page highlights some of the conjectures and open problems concerning L-functions, focussing on the areas in which there has been recent progress using results from Random Matrix Theory. Click on the subject to see a short article on that topic. If you would like to print a hard copy of the entire web page, you can download a postscript or pdf version. Distribution of zeros of L-functions The GUE hypothesis Correlations of zeros Neighbor spacing ... GOE and Graphs
Mesh Generation: Open Problems
ICS Theory Group ICS 280G, Spring 1997 Mesh Generation for Graphicsand Scientific Computation. open problems. We proved (4/3/97) the
http://www.ics.uci.edu/~eppstein/280g/open.html

Extractions: Mesh Generation for Graphics and Scientific Computation We proved ( ) the existence of triangulations of any polygon or straight line graph, and of convex quadrilateralizations of any orthogonal polygon. What about curved objects? Do spline-polygons have spline-triangulations? An example formed by connecting four quarter-ellipses shows Steiner points may be needed, even for quadratic splines, but maybe they only need to be added in the interior of the splinegon. On we went over dynamic programming techniques for optimal triangulation (e.g. minimum total edge length) of simple polygons, in O(n ) time or O(E ) if the visibility graph has E edges. So the slowest case is seemingly the most simple, when the polygon is convex. Can we find the minimum length triangulation of convex polygons in o(n ) time? Steve S. suggested Frances Yao's generalization of Knuth's speedup to optimal binary search tree construction (which has the same general dynamic programming form) but it doesn't seem to work. The same dynamic programming methods also work for optimal quadrilateralization, in time O(n
Home Page For Constructive Approximation Open Problem Section
Research problems section of the journal, edited by Peter Borwein, Albert Cohen, Ingrid Daubechies and Vilmos Totik. Includes problem statement (PostScript) and discussion.
http://www.cecm.sfu.ca/personal/pborwein/CA_MOSAIC/CA_problems.html

Extractions: Problems available online Return to the Constructive Approximation Homepage "I, Johann Bernoulli, greet the most clever mathematicians in the world. Nothing is more attractive to intelligent people than an honest, challenging problem whose possible solution will bestow fame and remain as a lasting monument. Following the example set by Pascal, Fermat, etc., I hope to earn the gratitude of the entire scientific community by placing before the finest mathematicians of our time a problem which will test their methods and the strength of their intellect. If someone communicates to me the solution of the proposed problem, I shall then publicly declare him worthy of praise." http://www.cecm.sfu.ca/personal/pborwein/CA_MOSAIC/CA_problems.html
Open Problems In Graph Theory Involving Steiner Distance
open problems involving Steiner distance.
http://www.uwinnipeg.ca/~ooellerm/open_problems/index.html

Extractions: This inequality does not hold for graphs in general as was shown by Henning, Oellermann, and Swart . It was shown in the same paper that for a graph G and n=3 and 4: diam n n G. It was shown by Oellermann and Tian that for a tree T: C n-1 (T) is contained in C n It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-center of a graph is contained in its Steiner n-center. It was shown by Beineke, Oellermann and Pippert that if T is a tree, then M n-1 (T) is contained in M n It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-median of a graph is contained in its Steiner n-median. Oellermann and Tian ). It is known that every graph is the 2-median of some graph (see Holbert ,and Hendry ). Steiner n-medians of trees have been completely characterized by
Problems In Analysis Of Algorithms
A list of open problems with updates and solutions.
http://pauillac.inria.fr/algo/AofA/Problems/

Extractions: Home Page Research Problems Bulletin board ... Resources Return to Analysis of Algorithms Home Page This page contains a list of interesting problems that we are aware of. You are encouraged to submit new ones by posting directly on the Bulletin Board . Typically 5 to 10 lines of TeX should be best for further editing. A digest of the main problems will be compiled here periodically by the Problem Editor Problem 1. Problem Solution ] By Conrado Martinez , 11-Jul-97. The depth of the j-th element in a random binary search tree of size n. Problem 2. Problem ] By Conrado Martinez , 11-Jul-97. Quicksort with median-of-three partitioning and halting on small subfiles. Problem 3. Problem Comments ] By Hsien-Kuei Hwang , 23-Jul-97. A limit distribution and zeros of a polynomial. Problem 4. Problem ] By Wojtek Szpankowski , 25-Jul-97. What is the distribution of node levels and height in digital search trees built on Bernoulli sources? Problem 5. Problem ] By Ed Coffman , 01-Aug-97. Analyse the waste in First-Fit bin-packing.
Open Problems On Perfect Graphs
Unsolved problems on perfect graphs.Category Science Math Combinatorics Graph Theory open problems In February of that year, Bruce and I prepared a list of open problems,which was then sent to all the invited participants. The
http://www.cs.rutgers.edu/~chvatal/perfect/problems.html

Extractions: (compiled by Maria Chudnovsky) A bibliography on perfect graphs Home pages of people interested in perfect graphs This collection is written for people with at least a basic knowledge of perfect graphs. Uninformed neophytes may look up the missing definitions on the web in Alexander Schrijver's lecture notes or in Jerry Spinrad's draft of a book on efficient graph representations etc. or in Eric Weisstein's World of Mathematics . Books on perfect graphs include M. C. Golumbic
Steiner Trees: Open Problems
open problems with Steiner Trees, maintained by Joe Ganley.Category Science Math Geometry open problemsganley.org The Steiner Tree Page - open problems. open problems.Of course, there are probably about a zillion open problems related
http://ganley.org/steiner/open.html

Extractions: ganley.org The Steiner Tree Page Of course, there are probably about a zillion open problems related to Steiner trees, but here are a few I've thought about. Please email me others if you like, and I'll include them here. Full trees Hwang's theorem allows us to construct an optimal rectilinear Steiner tree of a full set in linear time. I know of no other metric or type of graph in which computing the optimal Steiner tree of a full set is polynomial-time solvable but computing a general Steiner tree is NP-hard. Note that there isn't even a sufficiently strong analogue of Hwang's theorem for rectilinear Steiner trees in three dimensions. Multidimensional rectilinear Steiner ratio . What is the rectilinear Steiner ratio in arbitrary dimension d ? It is at least 2-1/ d , as the d -dimensional analogue of the "cross" has this ratio. It is obviously at most 2. It is generally believed that the lower bound is correct, but this hasn't been proven. Even an upper bound lower than 2 would be interesting. Rectilinear Steiner arborescence . These are Steiner-like trees on points in the (first quadrant of the) plane, in which every segment in the tree is directed left to right or bottom to top. It is unknown whether computing an RSA is NP-complete. (A good reference to start with is
Unsolved Problems
Including the list of 50 problems of Bondy and Murty with current status. Compiled by Stephen C. Locke.Category Science Math Combinatorics Graph Theory open problems A good paper on open and solved cageproblems is PK Wong, Cages-A Survey,, JGT,Vol.6 (1982) 1-22 Newer results can be found on Gordon Royle's www-Page http
http://www.math.fau.edu/locke/unsolved.htm

Extractions: You can contact Stephen C. Locke at LockeS@fau.edu Several people have asked me about unsolved problems. I will take the easy way out: see the list of 50 problems in Bondy and Murty . I hope it will not annoy the authors of that text if I will reproduce that list here, and perhaps (eventually) add to it. Problems number above 50 are from other sources. Some of these problems have been solved (and thus the title is slightly incorrect) and I won't claim to be familiar with all current results. If you find that one of them has been solved (or even that some reasonable progress has been made), please e-mail me . Also, I'm not giving you all of the references in Bondy and Murty . You should get yourself a copy of that book. Problems 26-56 Problems 57-61 The reconstruction conjecture . (S.M. Ulam, 1960) 2. A graph G is embeddable in a graph H if G is isomorphic to a subgraph of H . Characterise the graphs embeddable in the k -cube. (V.V. Firsov, 1965) 3. Prove: Every 4-regular simple graph contains a 3-regular subgraph. (N. Sauer, 1973)
Open Problems Columns - Douglas B. West
open problems Columns Douglas B. West. Thispage has moved. Please update your bookmark.
http://www.math.uiuc.edu/~west/pcolink.html
Interval Computations
Presents a guide to Interval Arithmetic research featuring open problems, applications, generalizations, bibliography, researchers' sites, ftp site, mailing list, etc.
http://www.cs.utep.edu/interval-comp/
Ideas, Concepts, And Definitions
open problems. open problems are not a source of frustration, they are asource of delight. open problems are the lifeblood of mathematics.
http://www.c3.lanl.gov/mega-math/gloss/math/openpr.html

Extractions: In a community of mathematicians, an open problem is a question that no one has found the answer to. Open problems are not a source of frustration, they are a source of delight. Open problems are the lifeblood of mathematics. For you, as an individual mathematician, your own open problems are the questions you raise that you cannot answer. Anyone who does mathematics for very long soon discovers that open problems are abundant, and even more of them are generated as mathematicians think about something and ask themselves questions in an effort to understand it. One of a mathematician's hardest choices is deciding which open problems to give focused attention to and try to solve. When you raise a question for yoursef, and you cannot answer it, it becomes an open problem for you. It is a good idea to share this problem with other mathematicians friends, classmates, teachers, etc. to see if they know of a solution or have ideas about solving it. Share your open problems with MegaMath! Don't abandon your open problems just because they remain unsolved for a long time. Set them aside and think about them gently . A solution might surprise you and arrive when you least expect it. You might even dream it!
Open Problems In Graph Theory Involving Steiner Distance
open problems involving Steiner distance.Category Science Math Combinatorics Graph Theory open problemsSome open problems in Graph Theory. It has been shown by Chartrand,Oellermann, Tian, and Zou that, for a tree T diam n T = n/(n
http://www.uwinnipeg.ca/~ooellerm/open_problems/

Extractions: This inequality does not hold for graphs in general as was shown by Henning, Oellermann, and Swart . It was shown in the same paper that for a graph G and n=3 and 4: diam n n G. It was shown by Oellermann and Tian that for a tree T: C n-1 (T) is contained in C n It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-center of a graph is contained in its Steiner n-center. It was shown by Beineke, Oellermann and Pippert that if T is a tree, then M n-1 (T) is contained in M n It remains an open problem to determine whether this containment holds for general graphs. In other words, it is not known if the Steiner (n-1)-median of a graph is contained in its Steiner n-median. Oellermann and Tian ). It is known that every graph is the 2-median of some graph (see Holbert ,and Hendry ). Steiner n-medians of trees have been completely characterized by
Open Problems On Graph Minors
By Nathaniel Dean.
http://dimacs.rutgers.edu/~nate/publics/open.ps
The RTA List Of Open Problems
The RTA list of open problems. The RTA 98. We are currently workingto transform the list of open problems into a WWW service. This
http://www.lsv.ens-cachan.fr/~treinen/rtaloop/

Extractions: The RTA list of open problems The RTA list of open problems summarizes open problems in the field of the International Conference on Rewriting Techniques and Applications (RTA). For the RTA 2002 conference, the topics of RTA were given as The RTA list of open problems was created in 1991 by Nachum Dershowitz Jean-Pierre Jouannaud and Jan Willem Klop on occasion of the RTA'91 conference. Updated lists have since been published at RTA'93, RTA'95 and RTA'98.

21-40 of 152 Back | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Next 20