Problem of the Week
Math Club
BUGCAT 2020
Zassenhaus Conference
Hilton Memorial Lecture
BingAWM
Organizers: Laura Anderson, Michael Dobbins, Seunghun Lee, and Thomas Zaslavsky.
Tuesday, 2/16
Organizational meeting
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 2/23
Title: What I've Been Doing, Part I
Speakers: Thomas Zaslavsky, James West, Michael Dobbins
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 3/2
Title: What I've Been Doing, Part II
Speakers: Olakunle Abawonse, Seunghun Lee
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 3/9
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 3/16
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 3/23
Title: Chi-Boundedness
Speaker: Peter Maceli (Ithaca)
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? In the early 1980’s András Gyárfás made a number of challenging conjectures about this. I will give a survey of how these questions seek to generalize the class of perfect graphs, along with some recent results.
Tuesday, 3/30
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 4/6
Title:
Speaker: Laura Anderson
Time: 1:15-2:15
This will be related to a talk by Kunle Abawonse the previous week in the Topology Seminar.
Zoom meeting id: 953 0238 3985
Tuesday, 4/13
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 4/20
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 4/27
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 5/4
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 5/11
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 5/18
Title:
Speakers:
Time: 1:15-2:15
Zoom meeting id: 953 0238 3985
Tuesday, 9/8
Title: Like speed dating, except combinatorics
Speakers: Michael Dobbins, Laura Anderson, Tom Zaslavsky
Time: 1:10-2:10
Zoom meeting id: 925 2894 7102
Today some of us will give very brief introductions to our current research.
Tuesday, 9/15
Title: Like speed dating, except combinatorics, part 2
Speakers: Nick Lacasse, Seunghun Lee
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
Tuesday, 9/22
Title: Like speed dating, except combinatorics, part 3
Speakers: Chris Eppolito, Kunle Abawonse
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
Tuesday, 9/29
Speaker: Thomas Zaslavsky (Binghamton)
Title: Structure for Signed Graphs
Time: 1:15 - 2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
A signed graph is a graph whose edges are labelled positive or negative. I survey a selection of aspects of signed-graph structure, beginning with Harary's founding “Structure Theorem” and including edges in circles, kinds of connection, a signed Kuratowski-type theorem, and structures that guarantee negative circles are not very disjoint.
Tuesday, 10/6
Speaker: Tillmann Miltzow (Utrecht University)
Title: A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Time: 1:15-2:15
Zoom meeting id: 925 2894 7102
Given a closed simple polygon P, we say two points p,q see each other if the segment pq is fully contained in P. The art gallery problem seeks a smallest set G of guards that sees P completely. Previous algorithms for the art gallery problem either had theoretical run time bounds (not necessarily good ones) but were utterly impractical, or were practical but could take forever on certain inputs without ever terminating. I present an algorithm that has both theoretical guarantees and practical performance.
This is joint work with Simon Hengeveld.
Tuesday, 10/13
Speaker: Shira Zerbib (Iowa State)
Title: Cutting Cakes with Topological Hall
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
An r-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set that has constant degree in each vertex side. Using a topological version of Hall's theorem, I prove bounds on the matching number of such hypergraphs. Combined with an approach of Meunier and Su (2018), this yields results on envy-free division of multiple cakes, and on rental harmony with multiple houses.
This is joint work with Ron Aharoni, Eli Berger, Joseph Briggs and Erel Segal-Halevi.
Tuesday, 10/20
Speaker: Geva Yashfe (Hebrew University of Jerusalem)
Title: Representability of $c$-Arrangements
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
This talk is about two undecidability results in matroid theory and their applications to secret-sharing and to the study of rank inequalities for representable matroids. After a brief discussion of the applications, I will outline a proof that the following problem, together with an approximate variant, is undecidable: given a matroid, decide whether its rank function has a positive multiple which is a representable polymatroid.
This is based on joint work with Lukas Kühne.
Tuesday, 10/27
Speaker: Michael Dobbins (Binghamton)
Title: Continuous Dependence of Curvature Flow on Initial Conditions in the Sphere
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
Consider the space of all simple closed curves of area 0 in the sphere that evenly divide the sphere. I will show that the restriction of level-set flow, which is a weakening of curvature flow, to this space is continuous. This was motivated by a problem of showing that the space of weighted pseudoline arrangements is homotopy equivalent to the corresponding rank 3 real Grassmannian.
Tuesday, 11/3
Speaker: Jo Ellis-Monaghan (Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam)
Title: An Introduction to Twualities
Time: 1:15-2:15
Place: Zoomland, opening at 11:45.
Zoom meeting id: 925 2894 7102
Zoomland LUNCH at noon with the speaker; all invited (no crowding, please).
We develop tools to identify and generate new surface embeddings of graphs with various forms of self-twuality including geometric duality, Petrie duality, Wilson duality, and both forms of triality (which is like duality, but of order three instead of two). Previous work typically focused on regular maps (special, highly symmetric, embedded graphs), but the methods presented here apply to general embedded graphs. In contrast to Wilson’s very large self-trial map of type {9,9}_9 we show that there are self-trial graphs on as few as three edges. We reduce the search for graphs with some form of self-twuality to the study of one-vertex ribbon graphs. Our results include a fast algorithm that will find all graphs with any of the various forms of self-twuality in the orbit of a graph that is isomorphic to any twisted dual of itself.
This is joint work with Lowell Abrams (George Washington University).
Tuesday, 11/10
Speaker: Seunghun Lee (Binghamton)
Title: The Near-$d$-Leray Property of Non-Matching Complexes
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
Given a graph $G$ on the fixed vertex set $V$, the non-matching complex of $G$, denoted by NM$_k(G)$, is the family of all subgraphs $G'$ of $G$ whose matching number $\nu(G')$ is strictly less than $k$. As an attempt to generalize a result by Linusson, Shareshian and Welker, we show that (i) NM$_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then NM$_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex NM$_k(G)$, which vanishes in all dimensions $d \geq 3k-4$, and all dimensions $d \geq 2k-3$ when $G$ is bipartite.
As a corollary, we have the following rainbow matching theorem, which generalizes a result by Aharoni et al. and Drisko's theorem: Given a graph $G=(V,E)$, let $E_1,\ldots, E_{3k-2}$ be non-empty edge sets (not necessarily disjoint), each colored with a different color, that cover $E$. If $\nu(E_i\cup E_j) \geq k$ for every distinct $i$ and $j$, then $G$ has a rainbow matching (where each edge has a different color) of size $k$. The number of edge sets $E_i$ can be reduced to $2k-1$ when $G$ is bipartite.
This is a joint work with Andreas Holmsen.
Tuesday, 11/17
Speaker: Vaidy Sivaraman (Mississippi State)
Title: Double-Threshold Graphs
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
A graph is double-threshold if there exists a weight assignment to its vertices and real numbers $L$, $U$ such that two vertices are adjacent if and only if the sum of their weights is between $L$ and $U$. The class of double-threshold graphs is closed under induced subgraphs but not under complementation. Kobayashi, Okamoto, Otachi, Uno asked whether the set of forbidden induced subgraphs for the class is finite. We answer this question negatively and make progress on determining the complete set of forbidden induced subgraphs.
This is joint work with Deven Gill.
Tuesday, 11/24
Speaker: Kunle Abawonse (Binghamton)
Title: Homeomorphism Type of Combinatorial Grassmannnian and Combinatorial Flag Manifold
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
I will consider combinatorial analogues to the Grassmannian G(2,n) and flag manifold G(1,2,n), denoted by MacP(2,n) and MacP(1,2,n) respectively. R. MacPherson conjectured that MacP(2,n) is homeomorphic to G(2,n), while it was later proven by Eric Babson that the manifolds are homotopy equivalent to their respective combinatorial analogues. I will establish that the manifolds are homeomorphic to their combinatorial analogues.
Tuesday, 12/1
Speaker: Benjamin Schröter (KTH Royal Institute of Technology)
Title: Reconstructibility of Matroid Polytopes
Paper: arXiv:2010.10227
Time: 1:15-2:15
Place: Zoomland, opening at 1:00.
Zoom meeting id: 925 2894 7102
My talk will deal with two fundamental objects of discrete mathematics that are closely related - (convex) polytopes and matroids. Both appear in many areas of mathematics, e.g., algebraic geometry, topology and optimization.
A classical question in polyhedral combinatorics is, 'Does the vertex-edge graph of a d-dimensional polytope determine its face lattice?'. In general the answer is no, but a famous result of Blind and Mani, and later Kalai, is a positive answer to that question for simple polytopes. In my talk I discuss this reconstructability question for the special class of matroid (base) polytopes. Matroids encode an abstract version of dependency and independency, and thus generalize graphs, point configurations in vector spaces and algebraic extensions of fields.
This is joint work with Guillermo Pineda-Villavicencio.
Tuesday, January 21
Virtual Combinatorics Colloquium
Speaker: Matjaz Konvalinka (Ljubljana)
Title: The First Bijective Proof of the ASM Theorem
Time: 2:00 - 3:00 (Note special time), preceded by a brief organizational meeting at 1:40
Room: WH-100E
Tuesday, January 28
No meeting today; we're all too busy.
Tuesday, February 4
Speaker: Laura Anderson (Binghamton)
Title: A Charming Conjecture Coming From Mathematical Psychology
Time: 1:15 - 2:15
Room: WH-100E
Tuesday, February 11
Speaker: Michael Dobbins (Binghamton)
Title: The Real RAM Analogue to the Cook--Levin Theorem
Time: 1:15 - 2:15
Room: WH-100E
Tuesday, February 18
No meeting today; we're warming up for next week's exciting talk.
Tuesday, February 25
Speaker: Ed Swartz (Cornell)
Title: Polymatroids are to Finite Groups as Matroids are to Finite Fields
Time: 1:15 - 2:15
Room: WH-100E
Tuesday, March 3
No meeting today.
Tuesday, March 10
Speaker: Chris Eppolito (Binghamton)
Title: Extension Spaces of Strongly Euclidean Oriented Matroids
Time: 1:15 - 2:15
Room: WH-100E
Tuesday, March 17
Speaker: Casey Donoven (Binghamton)
Title: Intersection Numbers and Minimal Subbases
Time: 1:15 - 2:15
Location: https://binghamton.zoom.us/j/951503518
The seminar will exist exclusively online, via Zoom. Casey will open the Zoom meeting at 1:00 to give time to work out any technical difficulties.
[Tuesday, March 24] POSTPONED: new date will be announced
Speaker: Olakunle Abawonse (Binghamton)
Title: Homeomorphism Types of the Combinatorial Grassmannian MacP(2,n) and the Combinatorial Flag Manifold MacP(1,2,n)
Time: 1:15 - 2:15
Location: TBA
Tuesday, March 31
No meeting today.
Tuesday, April 7
Virtual Combinatorics Colloquium
Speaker: Maria Chudnovsky (Princeton)
Title: Recent Progress on the Erdos--Hajnal Conjecture
Time: 2:00 p.m.
Location: https://smcvt.zoom.us/j/831984515
Tuesday, April 14
No meeting today $\because$ COVID-19.
Tuesday, April 21
Speaker: Amelia (Mattern) Cyr
Title: Deficiency in Signed Graphs
Time: 1:15 - 2:15, a break, and continuing for a while.
Location: https://zoom.us/j/96771786644?pwd=Q0Y4S2IveTVOU2ljZzdtV2F2bDdTUT09.
This is Ms. Cyr's doctoral dissertation defense. The examining committee consists of Laura Anderson, Michael Dobbins, Leslie Lander (outside examiner), and Thomas Zaslavsky (chair).
Saturday–Sunday, April 25–26, 2020 (virtual online meeting)
DISCRETE MATHEMATICS DAY at the University at Albany
Tuesday, April 28
Cancelled on account of COVID-19.
Tuesday, May 5
Cancelled on account of COVID-19.
Tuesday, June 9
Speaker: Nicholas Lacasse (Binghamton)
Title: A Survey of the Shi Arrangement
Time: 1:15 - 4:30 (with a break around 2:15)
Location: https://binghamton.zoom.us/j/92388564905 (opening at 1:00)
The Shi arrangement and its relatives like the Linial arrangement are arrangements of hyperplanes in Euclidean space that have gathered a lot of attention in recent years, not only from combinatorists. This talk, based on a paper of the same title by Susanna Fishel, will survey combinatorial aspects of the Shi arrangement.
This is Mr. Lacasse's exam for admission to candidacy. The examining committee consists of Laura Anderson, Michael Dobbins, and Thomas Zaslavsky (chair). The talk is open to the public and all are welcome.
Fall 2019 | Spring 2019 | Fall 2018 | Spring 2018 | Fall 2017 | Spring 2017 | Fall 2016 | Spring-Summer 2016 | Fall 2015 | Spring 2015 | Fall 2014 | Spring-Summer 2014 | Fall 2013 | Spring-Summer 2013 | Fall 2012 | Spring 2012 | Fall 2011 | Spring-Summer 2011 | Fall 2010 | Spring-Summer 2010 | Fall 2009 | Spring-Summer 2009 | Fall 2008 | Spring 2008 | Fall 2007 | Spring 2007 | Fall 2006 | Spring 2006 | Fall 2005 | Spring 2005 | Fall 2004 | Spring 2004 | Fall 2003 | Spring 2003 | Fall 2002 | Spring 2002 | Fall 2001 | Spring 2001 | Fall 2000 | Spring 2000 | Fall 1999 | Spring 1999 | Fall 1998 |