Title    name Lastest   |   Most hits   년도선택 최근 50건2012201120102009200820072006200520042003200220012000     KAIST Discrete Math Seminar Intertwining connectivities for matroids Tony Huynh (KAIST) 2012-02-29   An intertwine of two graphs G and H is a graph that has both G and H as a minor and is minor-minimal with this property. In 1979, Lovász and Unger conjectured that for any two graphs G and H, there are only a finite number of intertwines. This now follows from the graph minors project of Robertson and Seymour, although no ‘elementary’ proof is known. In this talk, we consider intertwining problems for matroids. Bonin proved that there are matroids M and N that have infinitely many intertwines. However, it is conjectured that if M and N are both representable over a fixed finite field, then there are only finitely many intertwines. We prove a weak version of this conjecture where we intertwine ‘connectivities’ instead of minors. No knowledge of matroid theory will be assumed. This is joint work with Bert Gerards (CWI, Amsterdam) and Stefan van Zwam (Princeton University).   KAIST Discrete Math Seminar Convex equipartitions of convex sets Alfredo Hubard (New York University) 2012-02-15   Imagine that you are cooking chicken at a party. You will cut the raw chicken fillet with a sharp knife, marinate each of the pieces in a spicy sauce and then fry the pieces. The surface of each piece will be crispy and spicy. Can you cut the chicken so that all your guests get the same amount of crispy crust and the same amount of chicken? We show that if the number of guests is a prime power, n=pk. Then such partition is possible. We derive this from a more general statement about equipartitions of convex bodies with respect to a measure and d-1 continuous functionals on the space of convex bodies, where d is the dimension the convex body sits in. Our proof uses optimal transport and equivariant topology.   KAIST Discrete Math Seminar Proving the Lovasz-Plummer Conjecture Andrew King (Simon Fraser University) 2012-02-08   In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds’ characterization of the perfect matching polytope. Joint work with Louis Esperet, František Kardoš, Daniel Král’, and Sergey Norin.)   KAIST Discrete Math Seminar Space Crossing Numbers Alfredo Hubard (HIT) 2012-02-01   We define a higher dimensional geometric analogue of the the crossing number of graph theory. The basic idea comes from the theory of line transversals and the Tverberg-Vrecica conjecture. Namely, we think of a crossing as a transversal 0-flat to a pair of edges or faces, and define space crossing as a transversal k-flat to a number of edges or faces. We obtain an almost tight space crossing number inequality that implies the classical crossing number inequality (up to a logaritmic factor). Joint work with Boris Bukh.   KAIST Discrete Math Seminar Lattice paths and Lagrangian matroids Edward D. Kim (POSTECH) 2012-02-01   We investigate lattice path Lagrangian matroids, a family of Lagrangian matroids introduced by Joe Bonin and Anna de Mier. One definition for Lagrangian matroids involves a construction of ordinary matroids. We discuss the corresponding relationship holds between lattice path Lagrangian matroids and lattice path matroids, proving one direction of a conjecture by de Mier relating lattice path Lagrangian matroids and lattice path matroids.   KAIST Discrete Math Seminar An analogue of Gromov’s waist theorem for coloring the cube Roman Karasev (Moscow Institute of Physics and Technology) 2012-02-01   It is proved that if we partition a d-dimensional cube into nd small cubes and color the small cubes into m+1 colors then there exists a monochromatic connected component consisting of at least f(d, m)=nd-m small cubes. The constant f(d,m) in our present approach looks quite ugly. In particular cases m=d-1 the question (and the answer) goes back to Lebesgue, the case m=1 was examined by Matousek and Privuetivy. They also conjectured the general case with other m. The same question was posed in informal discussions in Moscow by Alexey-Kanel-Belov. The proof will be based on (widely understood) Gromov’s method of contraction in the space of cycles. A different independent proof of a stronger fact was found by Marsel-Matdinov. Certain unsolved problems remain in this area. For example, Gromov’s question about extending the sphere waist theorem for maps into polyhedra which are not manifolds with bound depending only on the dimension.   KAIST Discrete Math Seminar Universality for families of non-crossing convex sets Michael Dobbins (KAIST) 2012-02-01   Mnev’s Universality theorem gives a construction showing that for any primary semialgebraic set, there is a family of points in the plane of fixed combinatorial type given by an oriented matroid such that the realization space of the family is homotopic to the semialgebraic set. Analogous universality results have also been shown for polytopes. Recently, we have found that the realization spaces of families of non-crossing convex sets in the plane with fixed combinatorial type are contractible, but that universality holds for families of non-crossing convex polygons with a bounded number of vertices.   KAIST Discrete Math Seminar Avoiding Large Squares in Partial Words Choi, Ilkyoo (University of Illinois at Urbana-Champaign) 2011-12-22   Given a fixed alphabet, a word of length n is an n-tuple with entries in the alphabet. A hole is a character outside the alphabet that is viewed as representing any letter of the alphabet. A partial word is a string where each character is a hole or belongs to the alphabet. Two partial words having the same length are compatible if they agree at each position where neither has a hole. A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words. This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.   KAIST Discrete Math Seminar Quartets in Weakly Compatible Split Systems Stefan Gruenewald (CAS-MPG Partner Institute for Computational Biolog) 2011-12-09   A phylogenetic (i.e evolutionary) tree can be interpreted as a compatible split system, that is a collection of bipartitions of a finite set X such that, for all four elements of X, there are no two bipartitions in the collection that induce different splits of those four elements into two pairs. Such a split of a 4-set into two 2-sets is called a quartet, and a split system is said to display a quartet, if there is at least one split in the system that induces this quartet. In phylogenetics, it is often useful to allow more general than compatible split systems, in order to display contradicting signals in the data or to find evidence for reticulate evolution. One natural such generalization are weakly compatible split systems, where for every 4-set at most two of the three possible quartets are allowed to be displayed. The split decomposition algorithm (implemented in the Splitstree software) is a successful tool to construct weakly compatible split systems from distance data. However, weakly compatible split systems are not as well understood as compatible ones. For example, maximal compatible split systems, i.e. compatible split systems which become incompatible whenever a new split is added, correspond to binary trees and display one quartet for every 4-set. In contrast, maximal weakly compatible split systems often display less than the two quartets per 4-set that are allowed by definition. Indeed there are examples where no quartet is displayed for almost all 4-sets. This leaves the question what is the minimum cardinality of maximal weakly compatible split systems for given cardinality of X. In my talk I will introduce weakly compatible split systems and explain their relevance for phylogenetics, and I will present upper and lower bounds for the smallest number of quartets in maximal weakly compatible split systems.   KAIST Discrete Math Seminar A New Class of Linear Codes for Cryptographic Uses Kim, Jon-lark (University of Louisville) 2011-11-25   We introduce a new class of rate one half codes, called complementary information set codes. A binary linear code of length 2n and dimension n is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune functions of use in the security of hardware implementations of cryptographic primitives. In this talk, we give optimal or best known CIS codes of length <132. We derive general constructions based on cyclic codes, double circulant codes, strongly regular graphs, and doubly regular tournaments. We derive a Varshamov-Gilbert bound for long CIS codes, and show that they can all be classified in small lengths up to 12 by the building up construction. This is a joint work with Claude Carlet, Philippe Gaborit, and Patrick Sole.   KAIST Discrete Math Seminar Approximating Max-Min Wighted T-join Satoru Iwata (RIMS, Kyoto University) 2011-11-11   Given an even subset T of the vertices of an undirected graph, a T-join is a subgraph in which the subset of vertices with odd degree is exactly T. Given edge weights, the weighted T-join problem is to find a T-join of minimum weight. With nonnegative edge weights, the problem can be reduced to finding a minimum weight perfect matching on the metric completion of the vertices in T. Given an undirected graph with nonnegative edge weights but no specific T, the Max-Min Weighted T-join problem is to find an even cardinality vertex subset T such that the minimum weight T-join for this set is maximum. The unweighted case of the problem when all weights are either unit or infinity has been well characterized by a decomposition of the underlying graph into factor critical and matching-covered bipartite subgraphs (Frank1993). We consider the weighted version which is NP-hard even on a cycle. After showing a simple exact solution on trees, we present a 2/3-approximation algorithm for the general case. Our algorithm is based on a natural cut packing upper bound obtained using an LP relaxation and uncrossing, and relating it to the T-join problem using duality. This is a joint work with R. Ravi.   KAIST Discrete Math Seminar Algorithms on Tree Decompositions and Time Improvements Hans L. Bodlaender (Utrecht University) 2011-10-31   Many problems that are intractable on general graphs become linear time solvable on graphs of bounded treewidth. The constant factor however of such algorithms is exponential or worse in the treewidth of the tree decomposition that is used. In this talk, a number of known and some new results are surveyed. In particular, it is shown how speed improvements can be obtained using convolutions, and how a recent technique called "cut-and-count" can be used to obtain fast probabilistic algorithms for problems like Hamiltonian Circuit.   KAIST Discrete Math Seminar Permutation Statistics on Signed Permutation Groups Jiang Zeng (Universite Claude Bernard Lyon-I) 2011-10-19   We generalize two bijections due to Garsia and Gessel to compute the generating functions of the two vector statistics (desG, maj, ℓG, col) and (desG, idesG, maj, imaj, col, icol) over the wreath product of a symmetric group by a cyclic group. Here desG, ℓG, maj, col, idesG, imajG, and icol denote the number of descents, length, major index, color weight, inverse descents, inverse major index, and inverse color weight, respectively. Our main formulas generalize and unify several known identities due to Brenti, Carlitz, Chow-Gessel, Garsia-Gessel, and Reiner on various distributions of statistics over Coxeter groups of type A and B.   KAIST Discrete Math Seminar On Diameters of Transportation and Network Flow Polytopes Edward D. Kim (POSTECH) 2011-10-14   Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters   KAIST Discrete Math Seminar Realizability of Antiprisms Michael Dobbins (KAIST) 2011-10-07   If one draws the Hasse diagram for the face lattice of a polytope, this may appear to be the 1-skeleton of some other polytope. In 1971 Lindström asked whether the intervals of a polytope’s face lattice ordered by containment can be realized as the face lattice of another polytope. If so, this would be the polytope appearing the Hasse diagram. In this talk, I will give necessary and sufficient conditions for the intervals of a polytope’s face lattice to be realizable, and I will provide a counter example showing that not every polytope satisfies these conditions.   KAIST Discrete Math Seminar Phase transitions in random graphs Kang, Mihyun (Freie Universitat Berlin) 2011-09-30   The phase transition deals with sudden global changes and is observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, for example, Potts models, graph colourings and random k-SAT. The phase transition in random graphs refers to a phenomenon that there is a critical edge density, to which adding a small amount a drastic change in the size of the largest component occurs. In Erdös-Renyi random graph, which begins with an empty graph on n vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches n/2 and a giant component emerges. Since this seminal work of Erdös and Renyi, various random graph models have been introduced and studied. In this talk we discuss phase transitions in several random graph models, including Erdös-Renyi random graph, random graphs with a given degree sequence, random graph processes and random planar graphs.   KAIST Discrete Math Seminar A conjecture on the (q,t)-binomial coefficients Shishuo Fu (KAIST) 2011-09-23   In one of their joint papers, Victor Reiner and Dennis Stanton introduced a (q,t)-generalization of the binomial coefficient. There was an interesting conjecture for the cases when q≤-2 is a negative integer. In this talk, I will prove this conjecture and try to give some combinatorial sense using integer partitions.   KAIST Discrete Math Seminar Convex representations of Oriented Matroids Andreas Holmsen (KAIST) 2011-09-16   Many combinatorial problems and arguments concerning finite point sets in the Euclidean plane (or higher dimensions) often do not use the linear structure. A more general concept is that of an Oriented Matroid (OM). It is well-known that every OM can realized by pseudolines, and in fact most oriented matroids can not be realized by straight lines. Recently, Alfreod Hubard (Courant Institute) and myself have found a new way to represent an OM by convex sets which retains much more of the “straightness” of the Euclidean plane. Interestingly, in our model the isotopy conjecture holds in a very strong sense, and it unifies several aspects of pseudoline arrangements.   KAIST Discrete Math Seminar Characteristic polynomials and the Bergman fan of matroids Huh, June (University of Michigan) 2011-07-28   Let V be a subvariety of the complex projective space. The amoeba of V is the set of all real vectors log|x| where x runs over all points of V in the complex torus. The asymptotic behavior of the amoeba is given by a polyhedral fan called the Bergman fan of V. We use the tropical geometry of the Bergman fan to prove the log-concavity conjecture of Rota and Welsh over any field. This work is joint with Eric Katz and is based on arXiv:1104.2519.   KAIST Discrete Math Seminar Improved bound on the phase transition for independent sets in the square lattice Eric Vigoda (Georgia Tech) 2011-07-14   The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree Δ≥3, is a well known computationally challenging problem. More concretely, let λc(TΔ) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite Δ-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λc(TΔ) as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice Z2, and provide a new lower bound for the uniqueness threshold, in particular taking it well above λc(T4). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z2 we prove that strong spatial mixing holds for all λ<2.3882, improving upon the work of Weitz that held for λ<27/16=1.6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution. This is joint work with Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Linji Yang. A preprint is available from the arXiv at: arxiv:1105.0914   KAIST Discrete Math Seminar Large and judicious bisections of graphs Lee, Choongbum (UCLA) 2011-07-07   It is very well known that every graph on n vertices and m edges admits a bipartition of size at least m/2. This bound can be improved to m/2 + (n-1)/4 for connected graphs, and m/2 + n/6 for graphs without isolated vertices, as proved by Edwards, and Erdős, Gyárfás, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree o(n) in fact contain a bisection which asymptotically achieves the above bounds. These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollobás and Scott on judicious bisections of graphs.   KAIST Discrete Math Seminar The maximum size of a Sidon set contained in a sparse random set of integers Lee, Sangjune (Emory University) 2011-06-09   A set A of integers is a Sidon set if all the sums $a_1$+$a_2$, with $a_1$≤$a_2$and $a_1$, $a_2$∈A, are distinct. In the 1940s, Chowla, Erdős and Turán showed that the maximum possible size of a Sidon set contained in [n]={0,1,…,n-1} is √n (1+o(1)). We study Sidon sets contained in sparse random sets of integers, replacing the ‘dense environment’ [n] by a sparse, random subset R of [n]. Let R=$[n]_m$ be a uniformly chosen, random m-element subset of [n]. Let F($[n]_m$)=max {|S| : S⊆$[n]_m$ Sidon}. An abridged version of our results states as follows. Fix a constant 0≤a≤1 and suppose m=m(n)=(1+o(1))$n^a$. Then there is a constant b=b(a) for which F($[n]_m$)=$n^b+o(1)$ almost surely. The function b=b(a) is a continuous, piecewise linear function of a, not differentiable at two points: a=1/3 and a=2/3; between those two points, the function b=b(a) is constant. This is joint work with Yoshiharu Kohayakawa and Vojtech Rödl.   KAIST Discrete Math Seminar Maximum hypergraphs without regular subgraphs Kim, Jaehoon (UIUC) 2011-06-03   We show that an n-vertex hypergraph with no r-regular subgraph has at most $2^n-1$+r-2 edges. We conjecture that if n>r, then every n-vertex hypergraph with no r-regular subgraph having the maximum number of edges contains a full star, meaning $2^n-1$ distinct edges containing a single vertex. We prove this conjecture for n≥425. This is joint work with Alexandr V. Kostochka.   KAIST Discrete Math Seminar Usage of Balloons in Regular Graphs O,Suil (UIUC) 2011-05-26   Petersen proved that every cubic graph without cut-edges has a perfect matching, but some graphs with cut-edges have no perfect matching. The smallest cubic graph with no perfect matching belongs to a general family applicable to many problems on connected d-regular graphs with n vertices. These include the smallest matching number for such graphs and a relationship between the eigenvalues and the matching number. In addition to these results, we present new results involving this family and the Chinese Postman Problem and a relationship between eigenvalues and edge-connectivity in regular graphs. This is partly joint work with Sebastian M. Cioaba and Doulgas B. West.   KAIST Discrete Math Seminar Fractional colouring of product graphs Xuding Zhu (Zhejiang Normal University) 2011-04-22   Given two graphs G and H, the categorical product G×H has vertex set V(G)×V(H), and two vertices (x,y) and (x′,y′) are adjacent if xx′E(G) and yy′E(H). The famous Hedetniemi-Lovasz Conjecture asserts that teh chromatic number of G×H equals the minimum of χ(G) and χ(H). In this talk, I will sketch a proof of the fractional version of the conjecture, which says that the fractional chromatic number of G×H equals to the minimum of the fractional chromatic numbers of G and H. This result is then used to prove a conjecture of Burr-Erdos-Lovasz on the chromatic Ramsey number of graphs.   KAIST Discrete Math Seminar A generalization of Kakeya's problem Otfried Cheong (KAIST) 2011-04-14   One version of Kakeya's problem asks for the smallest convex garden in which a ladder of length one can be rotated fully. The answer to this question was shown to be the equilateral triangle of height one by Pal in 1920. We consider the following generalization: Given a (not necessarily finite) family F of line segments in the plane, what is the smallest convex figure K such that every segment in F can be translated to lie in K? We show that as in the classic case, the answer can always be chosen to be a triangle. We also give an O(n log n) time algorithm to compute such an optimal triangle if F consists of n line segments. Joint work with Sang Won Bae, Hee-Kap Ahn, Joachim Gudmundsson, Takeshi Tokuyama, and Antoine Vigneron.   KAIST Discrete Math Seminar L(j,k) Labelings of Direct Product of Complete Graphs Rho, Yoomi (University of Incheon) 2011-03-17   An L(j,k) labeling of a graph is a vertex labeling such that the difference of the labels of any two adjacent vertices is at least j and that of any two vertices of distance 2 is at least k. The minimum of the spans of all L(j,k)-labelings of G is denoted by . Recently Haque and Jha proved if G is a direct product of complete graphs, then coincide with the trivial lower bound $(N-1)k$ where N is the order of G when j/k is within a certain bound. In this paper, we suggest a new labeling method of such a graph G. With this method, we extend the range of j/k such that holds. Moreover, we obtain an upper bound of for the remaining cases.   KAIST Discrete Math Seminar Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree Kim, Seogjin (Kunkuk University) 2011-03-10   Say that a graph with maximum degree at most d is d-bounded. For d>k, we prove a sharp sparseness condition for decomposability into k forests and a d-bounded graph. Consequences ar e that every graph with fractional arboricity at most k+ d/(k+d+1) has such a decomposition, and (for k=1) every graph with maximum average degree less than 2+2d/(d+2) decomposes into a forest and a d-bounded graph. When d=k+1, and when k=1 and d≤6, the d-bounded graph in the decomposition can also be required to be a forest. When k=1 and d≤2, the d-bounded forest can also be required to have at most d edges in each component.This is joint work with A.V. Kostochka, D.B. West, H. Wu, and X. Zhu.   KAIST Discrete Math Seminar Forbidden induced subgraphs of double-split graphs Kim, Ilhee (Princeton University) 2011-01-07   In the course of proving the strong perfect graph theorem, Chudnovsky, Robertson, Seymour, and Thomas showed that every perfect graph either belongs to one of five basic classes or admits one of several decompositions. Four of the basic classes are closed under taking induced subgraphs (and have known forbidden subgraph characterizations), while the fifth one, consisting of double-split graphs, is not. A graph is doubled if it is an induced subgraph of a double-split graph. We find the forbidden induced subgraph characterization of doubled graphs; it contains 44 graphs. This is joint work with Boris Alexeev, and Alexandra Fradkin.   KAIST Discrete Math Seminar Triangulations of Product of Simplices and Tropical Oriented Matroid Yoo, Hwanchul (MIT) 2010-12-22    In 2006 at MSRI, nine tropical geometers and combinatorialists met and announced the list of ten key open problems in (algebraic and combinatorial side of) tropical geometry. Axiomatization of tropical oriented matroids was one of them. After the work of Develin and Sturmfels, tropical oriented matroids were conjectured to be in bijection with subdivisions of product of simplices as well as with tropical pseudohyperplane arrangements. Ardila and Develin defined tropical oriented matroid, and showed one direction that tropical oriented matroids encode subdivision of product of simplices. Recently, in joint work with Oh, we proved that every triangulation of product of simplices encodes a tropical oriented matroid. In this talk, I will give a survey on this topic, and discuss this well known conjecture. I will also suggest a new class of combinatorial objects that may describe all subdivisions of a bigger class of polytopes.   KAIST Discrete Math Seminar Helly numbers and nerve theorems Xavier Goaoc (LORIA, INRIA Nancy – Grand Est) 2010-12-10   The Helly number of a collection of sets is the size of its largest inclusionwise minimal subfamily with empty intersection. The precise conditions that lead to bounded Helly numbers have been studied since the 1920′s, when Helly showed that the Helly number of any collection of compact convex sets in Rd has Helly number at most d+1. I will discuss a proof that any collection of subsets of Rd where the intersection of any subfamily consists of at most r connected components, each of which is contractible, has Helly number at most r(d+1). I will show how this implies, in a unified manner, quantitative bounds for several Helly-type theorems in geometric transversal theory. Our main ingredients are a new variant of the nerve, a “homological nerve theorem” for this structure and an extension of a projection theorem of Kalai and Meshulam. This is joint work with Eric Colin de Verdiere and Gregory Ginot.   KAIST Discrete Math Seminar On q-enumeration of permutations Shin, Heesung (POSTECH) 2010-11-19   Laguerre histories are certain colored Motzkin paths with some weight for each elementary steps. In this talk, we study two famous bijections between permutations and Laguerre histories, made by Francon-Viennot and Foata-Zeilberger. This two bijections are enable us to give permutations as combinatorial interpretations of continued fractions. The former is associated in linear statistics and the latter be in cyclic statistics. Using two mappings, we are able to make various results about several statistics of permutations.   KAIST Discrete Math Seminar Distance-Regular Graphs and Potential Theory Greg Markowsky (POSTECH) 2010-11-04   The study of electric potentials on graphs has a close connection with probability theory. On distance-regular graphs the theory is particularly elegant, as known results concerning such graphs allow explicit calculations to be made. In this talk, I will introduce these topics and discuss some recent results that Jacobus Koolen and I have obtained, as well as some conjectures and open problems.   KAIST Discrete Math Seminar On the free arrangements and truncated affine Weyl arrangements Masahiko Yoshinaga (Kyoto University) 2010-10-26   Freeness of a hyperplane arrangement is defined algebraically using module of derivations. I will discuss freeness of certain truncated affine Weyl arrangements, called the extended Catalan/Shi arrangements. I will also talk some enumerative corollaries.   KAIST Discrete Math Seminar Approximation algorithms for finding maximum stable matchings Shuichi Miyazaki (Kyoto University) 2010-10-15   The stable marriage problem is a classical matching problem. An input consists of the set of men, the set of women, and each person’s preference list that orders the members of the opposite sex according to the preference. The problem asks to find a stable matching, that is, a matching that contains no (man, woman) pair, each of which prefers the other to his/her current partner in the matching. One of the practical extensions is to allow participants to use ties in preference lists and to exclude unacceptable persons from lists. In this variant, finding a stable matching of maximum size is NP-hard. In this talk, we give some of the approximability results on this problem.   KAIST Discrete Math Seminar List coloring for geometric hypergraphs Shakhar Smorodinsky (Ben-Gurion University) 2010-09-17   Given a hypergraph H = (V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex whose color is distinct from the colors of all other vertices in S. The study of this notion is motivated by frequency assignment problems in wireless networks. We introduce and study the list-coloring (or choice) version of this notion. Joint work with Panagiotis Cheilaris   KAIST Discrete Math Seminar Quasi-randomness of graph properties Lee, Choongbum (UCLA) 2010-08-06   Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a random graph. They have been a subject of intensive study during the last two decades and have seen numerous applications both in Combinatorics and Computer Science. Starting with the work of Thomason and Chung, Graham, and Wilson, there have been many works which established the equivalence of various properties of graphs to quasi-randomness. In this talk, I will give a survey on this topic, and provide a new condition which guarantees quasi-randomness. This result answers an open question raised independently by Janson, and Shapira and Yuster.   KAIST Discrete Math Seminar The uplift principle and the Riordan group Lou Shapiro (Howard University) 2010-07-23   The Riordan group is an easy yet powerful tool for looking at a large number of results in combinatorial enumeration. At the first level it provides quick proofs for many binomial identities as well as a systematic way to invert them. We will see how they arise naturally when looking at the uplift principle as applied to classes of ordered trees. We will also discuss some recent results including the Double Riordan group, summer – winter trees, spoiled child trees, and will mention a few open problems as well. The main tools involved are generating functions, matrix multiplication, and elementary group theory.   KAIST Discrete Math Seminar Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs Huh, June (University of Illinois at Urbana-Champaign) 2010-07-09   The chromatic polynomial of a graph counts the number of proper colorings of the graph. We give an affirmative answer to the conjecture of Read (1968) and Welsh (1976) that the absolute values of the coefficients of the chromatic polynomial form a log-concave sequence. We define a sequence of numerical invariants of projective hypersurfaces analogous to the Milnor number of local analytic hypersurfaces. Then we show log-concavity of the sequence by answering a question of Trung and Verma on mixed multiplicities of ideals. The conjecture on the chromatic polynomial follows as a special case.   KAIST Discrete Math Seminar Matroids on convex geometries Yoshio Sano (POSTECH) 2010-05-14    The notion of a matroid was introduced by H. Whitney in 1935 as an abstraction of “linear independence” in a vector space. In 1960’s, J. Edmonds found that matroids are closely related to an efficient algorithm. After then, many researchers have studied and extended Matroid Theory. In 2007, S. Fujishige, G. A. Koshevoy, and Y. Sano introduced cg-matroids as an generalization of matroids. They defined a matroid-like structure on an abstract convex geometry, where the notion of an abstract convex geometry was introduced by P. H. Edelman and R. E. Jamison in 1985. In this talk, I will introduce the theory of cg-matroids. In particular, I will talk about the definition and some examples of cg-matroids, some combinatorial properties and characterization of cg-matroids, and the relationship between cg-matroids and the greedy algorithm.   KAIST Discrete Math Seminar Combinatorics on permutation tableaux Kim, Jangsoo (University of Paris 7) 2010-04-26   A permutation tableau is a relatively new combinatorial object introduced by Postnikov in his study of totally nonnegative Grassmanian. As one can guess from its name, permutation tableaux are in bijection with permutations. Surprisingly, there is also a connection between permutation tableaux and a statistical physics model called PASEP (partially asymmetric exclusion process). In this talk, we study some combinatorial properties of permutation tableaux. One of our result is a sign-imbalace formula for permutation tableaux which is very similar to the sign-imbalace formula for standard Young tableaux conjectured by Stanley.   KAIST Discrete Math Seminar A Combinatorial Formula for Information Flow in a Network Kook, Woong (University of Rhode Island) 2010-04-09   In 1989, Stephenson and Zelen derived an elegant formula for the information Iab contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Green’s function G, of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that Iab=(gaa+gbb-2gab)-1, where gij is the (i,j)-th entry of G. In this talk, we prove an intriguing combinatorial formula for Iab: Iab=k(G)/k(Ga*b).where k(G) is the complexity, or tree-number, of G, and Ga*b is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of Iab and the effective conductance between two nodes in electrical networks.   KAIST Discrete Math Seminar On the Number of Spanning Trees, Orientations, and Cycles Carsten Thomassen (Technical University of Denmark) 2010-04-02   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).   KAIST Discrete Math Seminar Approximate Shortest Path and Distance Queries in Networks Christian Sommer (University of Tokyo) 2010-03-26   We discuss how to efficiently compute shortest and approximate shortest paths in graphs, thereby focusing on shortest path query processing. The algorithm computing (approximate) shortest path queries is allowed to access a pre-computed data structure (often called distance oracle) in order to improve the query time. Several questions regarding such data structures are of particular interest: How can they be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality of the query result? What are the tradeoffs between pre-computation time, storage, query time, and approximation quality? For general dense graphs, the tradeoff between the storage requirement and the approximation quality is known up to constant factors. We discuss both the lower and the upper bound (by Thorup and Zwick). For specific types of sparse graphs, however, the exact tradeoff is not known; the general tradeoff can be improved: there are special data structures of a certain size that enable query algorithms to return distances of higher quality than what the general tradeoff would predict. We outline the state of the art of distance oracles for planar graphs and other classes of sparse graphs. We then prove that this improvement for some classes of sparse graphs cannot be extended to all sparse graphs: there is a three-way relationship between space, query time, and approximation quality for general sparse graphs. If time permits, we also cover space- and time-efficient data structures for certain complex networks with power-law degree sequences. Joint work with Wei Chen, Shinichi Honiden, Michael Houle, Ken-ichi Kawarabayashi, Shang-Hua Teng, Elad Verbin, Yajun Wang, Martin Wolff, and Wei Yu.   KAIST Discrete Math Seminar Polytope numbers Lee, Joonyop (KAIST) 2010-03-17   Polytope numbers for a polytope are a sequence of nonnegative integers which are defined by the facial information of a polytope. This is a higher dimensional generalization of polygonal number. It is well known that every polygon can be decomposed into triangles. A higher dimensional analogue of this fact states that every polytope has a triangulation, namely, it can be decomposed into simplices. Thus it may be possible to represent polytope numbers as sums of simplex numbers, which gives another way of calculating polytope numbers.In this talk, we define polytope numbers and calculate polytope numbers for several polytopes, and we introduce decomposition theorem, which is a way of representing polytope numbers as sums of simplex numbers. We also suggest further problems in the study of polytope numbers and possible approaches to these problems.   KAIST Discrete Math Seminar The 3-Color Problem Tommy R. Jensen (Kyungpook National University) 2010-02-19   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.   KAIST Discrete Math Seminar The Fibonacci dimension of a graph Sergio Cabello (University of Ljubljana) 2010-02-10   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.   KAIST Discrete Math Seminar Generalized Hamiltonian Cycles Jakub Teska (University of West Bohemia) 2010-01-28    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.   KAIST Discrete Math Seminar Total fractional colorings of graphs with large girth Daniel Kral’ (Charles University) 2010-01-26    A total coloring is a combination of a vertex coloring and an edge coloring of a graph: every vertex and every edge is assigned a color and any two adjacent/incident objects must receive distinct colors. One of the main open problems in the area of graph colorings is the Total Coloring Conjecture of Behzad and Vizing from the 1960’s asserting that every graph has a total coloring with at most D+2 colors where D is its maximum degree. Fractional colorings are linear relaxation of ordinary colorings. In the setting of fractional total colorings, the Total Coloring Conjecture was proven by Kilakos and Reed. In the talk, we will present a proof of the following recent conjecture of Reed. For every real ε>0 and integer D, there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number at most D+1+ε. Joint work with Tomás Kaiser, František Kardoš, Andrew King and Jean-Sebastien Sereni   KAIST Discrete Math Seminar New interpretations for noncrossing partitions of classical types Kim Jang Soo (University of Paris) 2010-01-21    The Catalan number 1/n+1(2n,n) is perhaps the most frequently occurred number in combinatorics. Richard Stanley has collected more than 170 combinatorial objects counted by the Catalan number. Noncrossing partition, which has received great attention recently, is one of these, so called, Catalan objects. Noncrossing partitions are generalized to each finite Coxeter group. In this talk, we will interpret noncrossing partitions of type B in terms of noncrossing partitions of type A. As applications, we can prove interesting properties of noncrossing partitions of type B.

Information Center for Mathematical Sciences KAIST 335 Gwahangno (373-1 Guseong-dong), Yuseong-gu, Daejeon 305-701, Republic of Korea TEL +82-42-869-8195~6, FAX +82-42-869-5722, e-mail : mathnet@mathnet.or.kr Copyright (c) 2009 by ICMS. All Rights Reserved