Bay Area Discrete Math Day- Fall 2016

Saturday, October 1st at UC Davis

The 33nd Bay Area Discrete Math Day (BAD Math Day) will take place at UC Davis on Saturday, October 1st, 2016. All talks will be held in Geidt 1003. (as seen on this campus map, or here).

BAD Math Days are one-day meetings aimed at facilitating communication between researchers and graduate students of discrete mathematics around the San Francisco Bay Area. These days happen twice a year and strive to create an informal atmosphere to talk about discrete mathematics. The term "discrete mathematics" is chosen to include at least the following topics: Algebraic and Enumerative Combinatorics, Discrete Geometry, Graph Theory, Coding and Design Theory, Combinatorial Aspects of Computational Algebra and Geometry, Combinatorial Optimization, Probabilistic Combinatorics, Combinatorial Aspects of Statistics, and Combinatorics in Mathematical Physics.

  • Registration
  • Speakers and Schedule
  • Directions and Parking
  • Carpooling
  • Organizers and Sponsors

  • Registration

    The registration deadline has passed.  Please email your local organizer or if you still wish to attend.


    All talks will he held in 1003 Giedt Hall.

    9:00-10:00am Welcome and refreshments
    Mimi Tsuruga
    University of California Davis

    Complex (simplicial) complexes

    Abstract: Given a d-dimensional simplicial complex K, can we determine whether K is a (PL-)sphere? For d ≤ 2, solutions to this problem have been known for over a century. When d = 3, the problem is in the complexity class NP. When d ≥ 5 it is undecidable. And for the missing dimension = 4, the complexity of this decision problem is still unknown. In practice, however, there are heuristic algorithms that can recognize a given complex to be a sphere (easily) in many situations. We will outline some heuristics---implemented in the topological software polymake---and discuss their limitations as well as some topologically interesting observations that we encountered in our experiments.

    Joint work with Michael Joswig and Frank H.~Lutz.
    Tyler Helmuth
    University of California Berkeley
    Title: Dimensional reduction for generalized continuum polymers

    Abstract: A striking example of dimensional reduction established by Brydges and Imbrie is an exact relation between the hard sphere gas in d dimensions and branched polymers in d+2 dimensions. I will discuss a new proof of this result, which also proves dimensional reduction formulas for generalized models of polymers associated to central hyperplane arrangements. The new proof is essentially combinatorial, in contrast to the original proof which uses supersymmetry.
    Christopher Hoffman
    University of Washington

    Title: Random Topology

    AbstractIn this talk we will survey recent results in random topology. The models that we will discuss include higher dimensions generalization of Erdos-Renyi random graphs, geometric random graphs and percolation. 
    12:30-2:00pm Lunch

    Ruriko Yoshida
    Naval Postgraduate School
    Convexity in treespaces

    AbstractWe study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all metrics or space of ultrametrics. The CAT(0)-metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric behave better. They exhibit properties desirable for geometric statistics, such as geodesics of small depth.  This is joint work with B. Lin, B. Sturmfels, and X. Tang.

    Annie Raymond
    University of Washington
    Symmetric sums of squares

    Many problems in extremal graph theory can be rephrased so that they ask to find sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by k-element subsets of [n].  To this end, we develop a variant of the Gatermann-Parrilo symmetry-reduction method tailored to this setting that allows for several simplifications and a connection to Razborov's flag algebras. We show that every symmetric polynomial that has a sos expression of a fixed degree also has a succinct sos expression whose size depends only on the degree and not on the number of variables. Our method bypasses much of the technical difficulties needed to apply the Gatermann-Parrilo method, and offers flexibility in obtaining succinct sos expressions that are combinatorially meaningful. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas. 
    Coffee break

    Anne Thomas
    University of Sidney

    Infinite reduced words and the Tits boundary of Coxeter groups

    AbstractLet (W,S) be a Coxeter system with W infinite. An infinite reduced word of W is an infinite sequence of elements of S such that each finite subsequence is a reduced word. We recall a natural partial order on infinite reduced words, called the limit weak order, which was investigated for affine W by Lam-Pylyavskyy. In order to study this partial order for non-affine W, we use techniques of geometric group theory, in particular the Davis complex X for (W,S). Our main result says that the limit weak order is encoded by the topology of the Tits boundary of X. No background on Davis complexes or the Tits boundary will be assumed. This is joint work with Thomas Lam (Michigan).

    Directions and Parking

    UC Davis can be reached by Amtrak from the Bay area or Sacramento.  Giedt Hall is approximately a 30 minute walk from the train station.  UC Davis can also be reached by Interstate 80 from the Bay Area (exit 27 to CA 113 North.  Merge onto Hutchinson Dr. and turn right onto La Rue for parking lot VP 47, the closest parking to Geidt Hall).  Parking is free on the weekends.


    If you need a ride, or if you are able to give rides, please contact your local member of the BAD Math Committee. 

    Organizers and Sponsors

    The BAD Math Committee:

    The 33nd BAD Math Day is kindly supported by the D.E. Shaw Group, Elsevier, and UC Davis: