31st Bay Area Discrete Math Day, Fall 2015

San Francisco State University

Saturday, October 17, 2015


BADMath 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.


pop up description layer

Program

9:00-10:00 Breakfast refreshments
10:00-10:30 Alexandra Kolla   How to Play Unique Games
Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, Max Cut. In this talk we will describe the Unique Games problem and give an overview of the state-of-the-art algorithmic results for Unique Games.
10:45-11:15 Tewodros Amdeberhan   Ladies and Gentlemen, Let's Count!
A classical result of Lucas allows counting non-zero coefficients of (1+x)n modulo primes. In this talk, we present generalizations to multivariate polynomials over fields K of positive as well as of zero characteristic. These types of questions are closely linked to lattice point enumerations in polytopes.
11:30-12:30 Jacob Fox   Combinatorial Packing Problems
Packing problems have been studied for more than four centuries, and have connections to diverse areas of pure and applied mathematics. In this talk, we focus on two well-studied combinatorial packing problems, Pippenger and Golumbic's graph inducibility problem from 1975 and Wilf's permutation packing problem from 1992. We discuss recent joint work with Hao Huang and Choongbum Lee which solves these problems in almost all instances.
12:30-2:00 Lunch
2:00-2:30 Eugene Gorsky   Rational Catalan Combinatorics
Classical Catalan numbers, in one of their many presentations, count lattice paths in a square which stay above the diagonal. Similarly, rational Catalan numbers count lattice paths in an arbitrary rectangle which stay above the diagonal. In recent years, rational Catalan numbers have been related to algebraic geometry of singular curves, combinatorics of affine symmetric groups and representation theory of Cherednik algebras. I will describe some of these connections, focusing on combinatorial structures underlying them.
2:45-3:15 Christine Klymko   Detecting Highly Cyclic Structure With Complex Eigenpairs
One important problem in the analysis of complex networks is the detection of communities and anomalous regions, especially when they do not follow traditional (modularity-based) rules for connectivity. In this work, we develop methods to detect highly cyclic subgraph topologies in directed networks via the calculation of eigenvectors associated with certain complex eigenvalues of the adjacency matrix. We characterize this phenomenon theoretically to understand the capabilities and limitations for utilizing eigenvectors in this venture, as well as show the results on some generated and real-world networks. Additionally, we discuss the application of these techniques to motif detection.
3:15-4:00 Coffee Break
4:00-5:00 Sara Billey   Trees, Tanglegrams, and Tangled Chains
Tanglegrams are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted binary trees. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched vertices, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This includes a new formula for the number of binary trees with n leaves. We also give a conjecture for the expected number of cherries in a large randomly chosen binary tree and an extension of this conjecture to other types of trees. This is joint work with Matjaz Konvalinka and Frederick (Erick) Matsen IV.
6:00-8:00 Dinner


Registration

... is now closed.


Directions and parking

Directions to San Francisco State University can be found on the SFSU website. If you are driving, we recommend that you park in Lot 20; it will cost you $5. Follow the parking instructions and the campus map.

All talks will take place in SCI 201. Please note that the Science Building is currently under construction. You will need to enter the building on the side of the main Quad, facing away from 19th Avenue.


Carpooling

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


Organizers/Sponsors

The BADMath Committee:


The 31th Bay Area Discrete Mathematics Day is kindly sponsored by

San Francisco State University       D.E. Shaw Elsevier