January 26th, 2010
On the Number of Spanning Trees, Orientations, and Cycles
Carsten Thomassen
Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
2009/04/02 Friday 4PM-5PM (Room: T.B.A.)
One of the most fundamental properties of a connected graph is the existence of a spanning tree. Also the number τ(G) of spanning trees is an important graph invariant. It plays a crucial role in Kirchhoff’s classical theory of electrical networks, for example in computing driving point resistances. More recently, τ(G) is one of the values of the Tutte polynomial which now plays a central role in statistical mechanics. So are a(G), the number of acyclic orientations, and c(G), the number of orientations in which every edge is in a directed cycle. As a first step towards convexity properties of the Tutte polynomial, Merino and Welsh conjectured that
τ(G) ≤ max{a(G),c(G)}
for every loopless and bridgeless multigraph G. We shall here prove that τ(G) ≤ c(G) for all loopless and bridgeless multigraphs with n vertices and at least 4n edges and that τ(G) ≤ a(G) for all loopless multigraphs with n vertices and at most 16n/15 edges. We also verify the conjecture for cubic graphs (which are in between these two bounds).
Tags: CarstenThomassen
Posted in 2010, KAIST Discrete Math Seminar | No Comments »
January 26th, 2010
FYI (Department Colloquium)
Rendezvous numbers and von Neumann’s min-max theorem
Carsten Thomassen
Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
2009/04/01 Thursday 4:30PM-5:30PM (Room 1501)
A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a.
O. Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s min-max theorem in game theory.
In an article in the American Math. Monthly 93(1986) 260-275, J. Cleary and A. A. Morris asked if a (more) elementary proof of Gross’ result exists.
In this talk I shall formulate a min-max result for real matrices which immediately implies these results of Gross and von Neumann.
The proof is easy and involves only mathematical induction.
Tags: CarstenThomassen
Posted in 2010, KAIST Discrete Math Seminar | No Comments »
January 15th, 2010
The 3-Color Problem
Tommy R. Jensen
Department of Mathematics, Kyungpook National University, Daegu, Korea
2009/02/19 Friday 4PM-5PM
The fundamental sufficient condition for the existence of a proper 3-coloring of the vertices of a planar graph G was proved by Grötzsch more than 50 years ago, and it requires that G has no triangles (cycles of length 3). This talk discusses conjectures for other possible sufficient conditions, some of which have stubbornly resisted proofs for decades, and also various recent partial results. A conjecture in a different direction deals with a stronger 3-colorability property, which for a planar graph turns out to be equivalent to triangle-freeness, but here it is unknown whether the assumption of planarity may be weakened.
Tags: TommyJensen
Posted in 2010, KAIST Discrete Math Seminar | No Comments »
January 14th, 2010
The Fibonacci dimension of a graph
2010/2/10 Wed, 4PM-5PM
The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into the f-dimensional Fibonacci cube. We will see combinatorial relations between the Fibonacci dimension and the isometric or lattice dimension, and establish the Fibonacci dimension for certain families of graphs. Finally, we will discuss the problem of computing the Fibonacci dimension, namely, its NP-hardness and approximation algorithms.
Joint work with D. Eppstein and S. Klavžar. Manuscript available at arxiv:0903.2507.
Tags: SergioCabello
Posted in 2010, KAIST Discrete Math Seminar | No Comments »
January 12th, 2010
Generalized Hamiltonian Cycles
Jakub TeskaDepartment of Mathematics, University of West Bohemia, Czech Republic
2010/1/28 Thu 4PM-5PM (E6-1 Room 2411 *1409*)
Hamiltonian cycle in a graph G is a cycle, which contains every vertex of the graph G. The problem of existence of a hamiltonian cycle in a graph is a well known NP-complete problem. While some theoretical necessary and sufficient conditions are known, to date, but no practical characterization of hamiltonian graphs has been found. There are several ways how to generalize the notion of a hamiltonian cycle.
For any integer r>1, an r-trestle is a 2-connected graph F with maximum degree ∆(F)≤ r. We say that a graph G has an r-trestle if G contains a spanning subgraph which is an r-trestle. This concept can be viewed as an interesting variation on the notion of Hamilton cycle. Another such variation is a concept of k-walks, where a k-walk in a graph G is a closed spanning walk visiting each vertex at most k times, where k is a positive integer.
We present several results and problems concerning mainly with k-walks and r-trestles and relations between them.
Tags: JakubTeska
Posted in 2010, KAIST Discrete Math Seminar | No Comments »
