The Combinatorics Research Workshop brings together faculty, postdocs, and advanced graduate students from all areas of combinatorics with the goal of forming teams and working on problems together. 

It is sponsored by the Mathematics PhD program at the Graduate Center. Please take a look at this page for our vision of the workshop and for directions to the Graduate Center, parking, lodging, and local attractions.

Location: All talks will be held in the Science Center on the 4th floor of the Graduate Center. 

Registration: There are no registration fees, but registration is required due to room capacity limitations. Please fill out this registration form as soon as possible. If we exceed room capacity, we may be able to reserve a larger room if it is done in a timely manner. 

We are making this workshop hybrid. The zoom link is 

https://us06web.zoom.us/j/86307956249?pwd=1Ap2I5zPazo4NOVHJ8MIFLXqvWfArj.1

Meeting ID: 863 0795 6249
Passcode: CRW2025

Schedule

Monday July 21

10:00 am: Ambat Vijayakumar (Regular Triangle Distinct Graphs and (r,c)-Graphs)

11:15 am: Mel Nathanson (Sumset Sizes in Additive Number Theory)

12:30 pm - 2:00 pm: Lunch

2:00 pm:  Joseph Fehribach (Kirchhoff Graphs)

3:15 pm: Wine and Cheese

Tuesday July 22

10:00 am: Aparna Lakshmanan (General Position and Mutual-Visibility Problems in Graphs

11:15 am: Kira Aradicheva (Structural and Computational Aspects of Implicational Bases of Matroids)

12:15 pm - 2:00 pm: Lunch

2:00 pm: Nadia Benakli  (Locating Vertices: An Introduction to Metric Dimension in Graphs)

3:15 pm: Kerry Ojakian (Hidden Reality in Cops and Robber)

4:30 pm: Wine and Cheese

Workshop Dinner 5:00 pm (Location TBA)

Wednesday July 23

10:00 am: Sandra Kingan (Excluded Minor Results in Graphs)

11:15 am: Benjamin Steinberg (Markov Chains, Matroids, Hyperplane Arrangements and Semigroups)

12:15 pm - 2:00 pm: Lunch

2:00 pm: Rohit Parikh (Amartya Sen's Capability Approach and the Graph Structure of Society) 

3:15 pm: Wine and Cheese

Thursday July 24

10:00 am: Eric Ramos (Finding Topology in a (Random) Factory)

11:15 am: Pablo Soberon (Bisections of Measures with Hyperplane Arrangements)

12:15 pm - 2:00 pm: Lunch

2:00 pm: Deepak Bal (Generalized Ramsey and Anti-Ramsey problems)

3:15 pm: Wine and Cheese

Speakers (in alphabetical order)

Speaker: Kira Adaricheva (Hofstra University)

Title:  Structural and Computational Aspects of Implicational Bases of Matroids

Abstract: All finite lattices are lattices of closed sets of some closure operators, and closure operators can be defined by sets of implications. Some concise sets of implications representing a closure operator are well known in computer science in the form of implicational bases, which offer challenging optimization problems. Recently a new form of a (partial) implicational base was suggested, which is called the E-base, pertinent to a structural property studied in free lattices, and a new class of finite lattices was shown to have a valid E-base (arxiv2502.0446). The same class was a target of somewhat related effort to describe the Frattine sublattice of a lattice, which is the intersection of all maximal sublattices. 

The matroids are typically defined through two types of hypergraphs: the circuits and the independent sets/bases, but there is an associated closure operator that allows to think of matroids as lattices as well, known as geometric lattices. Not much is known about implicational bases of matroids, but some work was done in the last century by P. Vanderlind, A. Dress, W. Wenzel and M. Wild. More recently, K. Berczi, E. Boros and K. Makino (2024) (arxiv230.06642) introduced matroid Horn functions, which could be considered a special form of implicational bases, and studied their optimization in the number of circuit clauses.

A number of interesting problems remain such as describing the subclasses of matroids where the E-base is valid, recognizing geometric lattice/matroid Horn function from an implicational base or computation of the Frattini sublattice of a geometric lattice.

Speaker: Ambat Vijayakumar (Cochin University of Science and Technology, India)

Title: Regular Triangle Distinct Graphs and (r, c)-Graphs

Abstract: We shall discuss the notions of regular triangle distinct graphs [1,6] and $(r, c)$-graphs [2], both motivated by our results in [4, 5]. In an attempt to settle a conjecture of A. Kotzig [3], the notion of triangle degree (triangle number) - number of triangles in a graph G containing a vertex $v$ denoted by $t(v)$ was introduced in [4]. A graph is triangle distinct if every vertex has distinct triangle degree. While there cannot be a simple graph with all distinct degrees, there are graphs with distinct triangle degrees. In[1] a recursive construction of triangle distinct graphs is provided, starting from the smallest one such, of order seven. In[1],  Z.Berikkyzy et al., have posed an open problem, does there exist regular triangle distinct graphs? In [6], Stevanovic et al. have constructed arbitrary large family of regular triangle distinct graphs using some results in [5].  Some properties of such graphs will also be discussed. 

$(r, c)$-graphs are $r$-regular graphs in which the subgraph induced by the open neighbourhood of every vertex has precisely $c$ edges. This family of graphs contains, vertex-transitive graphs (in particular Cayley graphs and circulants) and strongly regular graphs. It is noted that $(r, c)$- graphs are precisely strongly vertex triangle regular graphs studied in [5]. $(r, c)$-planar graphs and $(r, c)$ - circulants will also be discussed.

References:

1. Z. Berikkyzy, B. Bjorkman, H. S. Blake, S. Jahabekam, L. Keough, K. Moss, D. Rorabaugh, S. Shan, Triangle-degree and triangle-distinct graphs, Discrete Mathematics (2024).

2. Y. Caro, X. Mifsud, On $(r, c)$- constant, planar and circulant graphs, DMGT (2025).A. Kotzig, Selected open problems in graph theory, J. A. Bondy, U. S. R. Murty (Eds.), Graph theory and related topics (AP,1979).

3. B. Radhakrishnan Nair, A. Vijayakumar, About triangles in a graph and its Complement, Discrete Math (1994).

4. B. Radhakrishnan Nair, A. Vijayakumar, Strongly edge triangle regular graphs and a conjecture of Kotzig, Discrete Mathematics (1996).

5. D. Stevanovic, M. Ghebleh, G. Caporossi, Ambat Vijayakumar, Sanja Stevanovic, On regular triangle distinct graphs, Computational and Applied Mathematics (2024).

Speaker: Deepak Bal (Montclair State University)

Title:  Generalized Ramsey and Anti-Ramsey Problems 

Abstract: Fix a graph $H$. Suppose you want to color the edges of some large host graph $G$ such that every copy of $H$ receives at least $q$ colors. You can think of this as a "local heterogeneity" condition. Of course if we are willing to use a lot of colors (say, $|E(G)|$ many) then this is a trivial task. Minimizing the total number of colors used is known as a generalized Ramsey problem, and the solution to this optimization is denoted $f_R(G,H,q)$. Thus generalized Ramsey problems are about understanding a tradeoff of the form "local diversity vs. global homogeneity."

One may naturally wonder about the opposite tradeoff: "local homogeneity vs. global diversity." In this scenario, we want to color the edges of $G$ such that every copy of $H$ sees at most $q$ colors. Of course, if we only use $1$ color on the edges of $G$, then the condition is certainly satisfied. Maximizing the total number of colors used is known as a generalized anti-Ramsey problem and the solution to the optimization problem is denoted $f_{AR}(G,H,q)$.

In this talk I'll discuss some history and recent progress on various cases of the above problems. Many open problems and unexplored avenues of research remain.

Speaker: Nadia Benakli (New York City College of Technology, CUNY)

Title:  Locating Vertices: An Introduction to Metric Dimension in Graphs

Abstract: How many landmarks are needed to determine the location of an object in a network? To answer this question, the concept of metric dimension, a graph invariant, was introduced. This talk will cover a couple of known results and offer a brief look at some open questions.

Speaker: Joseph Fehribach (Worcester Polytechnic Institute)

Title: Kirchhoff Graphs

Abstract: Given a set of $n$ vectors in any vector space over the rationals, suppose that $k$ are linear independent ($1<k<n$). Kirchhoff graphs are vector graphs (graphs whose edges are these vectors), whose cycles represent the dependencies of these vectors and whose vertex cuts are orthogonal to these cycles. This presentation discusses some of the basics of Kirchhoff graphs, Kirchhoff graph uniformity and how tiling can generate families of Kirchhoff graphs. These families are composed of prime graphs (those having no Kirchhoff subgraphs), and composite graphs (not prime), all generated by a set of fundamental Kirchhoff graphs (smallest prime Kirchhoff graphs that can generate other prime and composite graphs for our set of vectors). There will also be a list of open questions.

References:

T. M. Reese, J. D. Fehribach, R. C. Paffenroth, B. Servatius, Uniform Kirchhoff graphs, Linear Algebra and its Applications, Vol 566, 2019, 1-16,

Speaker: Sandra Kingan (Brooklyn College and the Graduate Center, CUNY)

Title: Excluded Minor Results in Graphs

Abstract: A striking phenomenon in graph theory is the relationship between structural properties and forbidden minors. For any graph $G$, we often encounter the dichotomy: either $G$ has a particular structure or it contains specific minors, and crucially, not both. Results of this type can be divided naturally into two classes depending on whether they are motivated by the structure imposed or by the minors excluded.

In the first case, given a class of graphs with a certain structure, we ask whether the class can be characterized precisely in terms of a finite list of minimal excluded minors. The foundational result in this domain is the 1937 Kuratowski-Wagner theorem: a graph is planar if and only if it has no $K_5$- or $K_{3,3}$-minor.  In the second case we fix a set of forbidden minors and explore the resulting graph class. It is customary to focus on 3-connected graphs, since a graph that is not 3-connected can be constructed from its 3-connected proper minors via direct sums and 2-sums. 

For example, in 1937 Wagner proved that a 3-connected graph has no $K_5$-minor if and only if it is the Mobius ladder $V_8$ or the 3-sum of 3-connected planar graphs. In 1943 D. W. Hall noted that a 3-connected graph has no $K_{3,3}$-minor if and only if it is planar or $K_5$. Later, in 1960 Wagner noted that a 3-connected graph has no $K_5\backslash e$-minor if and only if it is $K_{3,3}$ or the geometric dual of $K_5\backslash e$ (also known as the prism graph), or the wheel graph $W_{n-1}$ for $n\ge 4$. In 1963 Dirac proved that a 3-connected graph has no prism-minor if and only if it is a wheel, $K_5$, $K_{3, n-3}$, $K'_{3, n-3}$, $K''_{3, n-3}$, $K'''_{3, n-3}$ for $n\ge 6$.  

We will examine these classical theorems using modern techniques with the goal of developing new excluded minor theorems. Our approach draws on recent developments in matroid structure theorems. Of special interest is the long-standing open problem of characterizing the 3-connected graphs with no minor isomorphic to the Petersen graph, a problem that remains one of the most celebrated and elusive in the theory of graph minors.

Speaker: Aparna Lakshmanan (Cochin University of Science and Technology, India)

Title: General position and Mutual-Visibility Problems in Graphs

abstract: The graph general position problem reflects the Dudeney's no-three-in-line problem [3] as well as the general position subset selection problem from discrete geometry [4]. The problem was in a different context investigated on hypercubes [5], while it was introduced in its generality as follows [6]. A set $S$ of vertices in a graph is a general position set if no three vertices from $S$ lie on a common shortest path. A largest general position set of a graph $G$ is called a gp-set of $G$ and its size is the general position number $gp(G)$ of $G$. The same concept was in use two years earlier in [1] under the name geodetic irredundant sets, where it was defined in a different way.

In discrete geometry, a shortest path between two points is unique while in graphs there can be more than one shortest path between two vertices. This fact, as well as the computational concept of visibility between robots bring the mutual-visibility problem in graphs into picture. This problem was introduced by Di Stefano [2] as follows. Given a set S of vertices in a graph $G$, two vertices $u$ and $v$ are mutually-visible or, more precisely, $S$-visible, if there exists a shortest $uv$-path in $G$ which contains no further vertices from $S$. The set $S$ is a mutual-visibility set if its vertices are pairwise mutually-visible. A largest mutual-visibility set is called a $\mu$-set and its size is called the mutual-visibility number $\mu(G)$ of $G$.

In this talk we will be discussing about the general position and mutual visibility in certain graph classes.

References

1. U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135--143.

2. G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) Paper 126850.

3. H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917.

4. V. Froese, I. Kanj, A. Nichterlein, R. Niedermeier, Finding points in general position, Internat. J. Comput. Geom. Appl. 27 (2017) 277--296.

5. J. Korner, On the extremal combinatorics of the Hamming space, J. Comb. Theory Ser. A 71 (1995) 112--126.

6. P. Manuel, S. Klavzar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177--187.

Speaker: Melvyn Nathanson (Lehman College and the Graduate Center, CUNY)

Title: Sumset Sizes in Additive Number Theory 

Abstract:  The $h$-fold sum of a set $A$ of integers, denoted $hA$, is the set of integers that can be represented as a sum of $h$ not necessarily distinct elements of $A$.  It is an important unsolved problem to determine the set $R(h, k)$ of all possible $h$-fold sumset sizes of a set of $k$ integers.  Recent results and related open problems on this subject will be discussed.

Speaker: Kerry Ojakian (Bronx Community College, CUNY)

Title: Hidden Reality in Cops and Robbers

Abstract: This is in-progress joint work with Nancy Clarke and Danny Dyer. I will consider the classic graph-theoretic game of cops and robber, with a twist: certain information will be hidden from one of the two players. A motivation for this twist (which could be applied to many graph-theoretic games) is to better understand the underlying properties of strategies. In the classic game, one player controls a single robber, while another player controls some number of cops; the game

is played on a connected simple graph. The players alternate turns, where on a player's turn, for each of their pieces, they can move it to adjacent vertex or the piece can remain where it is. The goal of the cops is for a cop and robber to occupy the same vertex; the goal of the robber is to avoid this. 

In our twist, given some graph $G$, the vertices are labeled in any manner, where the same label may be assigned to distinct vertices. The labeled contraction of $G$ (denote \contract{G}) is obtained as follows: for each label $k$, perform the standard vertex contraction on all the vertices in $G$ with label $k$, so they become a single vertex; if there is an edge in $G$ from any vertex labeled $j$ to any vertex labeled $k$, then in \contract{G}, there is an edge from the one vertex $j$ to the one vertex $k$. For example, if G is $P_5$ labeled like this- $(v, x, x, x, w)$, then \contract{G} is $P_3$ labeled like this- $(v, x, w)$. While both players are actually in G, one of the players (the ``appearence player") will only know its locations as given by \contract{G}. When the appearence player specifies a move, say from $j$ to $k$, in \contract{G}, the move is naturally interpreted as a move actually occurring in $G$: the piece is moved from $j$ to an adjacent vertex also labeled $j$, on a path that leads towards a vertex labeled $k$ (if there are multiple such paths, then the opponent adversarially chooses).

For example (keeping with the previous path example), if there is one cop, and that cop is the appearence player, then if the cop is at one of the 3 $x$'s in $P_5$, she sees herself as being at the one $x$ in $P_3$. While the cop's information is limited, she is given enough information to win: She could specify to start at $v$, then move to $x$, and once at $x$ to move to $w$. The cop's intention to move from $x$ to $w$ will mean that the cop is moved to an $x$ in the direction of $w$, thus the cop will eventually reach $w$ and so win.

In fact any path $P_n$ could be labeled like the $P_5$, with distinct endpoint labels $v$ and $w$, while the other $(n - 2)$ middle vertices all get label $x$. Any such path contracts to the same $P_3$ and the same strategy on $P_3$ works for any $P_n$. This small example on paths brings out one of the key motivations of this work: in a precise way, we can describe the core logic for a winning strategy on paths, by giving an appropriate labeling and then describing a strategy on the contracted graph. The big goal of this work is to obtain a more general understanding of strategy in the context of cops and robber, as well as other graph-theoretic games.

Speaker: Rohit Parikh (Brooklyn College and the Graduate Center)

Title: Amartya Sen's Capability approach and the Graph Structure of Society 

Abstract: ``The capability approach is a theoretical framework that entails two normative claims: first, the claim that the freedom to achieve well-being is of primary moral importance and, second, that well-being should be understood in terms of people’s capabilities and functionings." --Ingrid Robeyns and Morten Fibieger Byskov, (Stanford Encyclopedia of Philosophy)

``Whether you should sleep on your back or on your belly is a matter in which the society should permit you absolute freedom, even if a majority of the community is nosey enough to feel that you must sleep on your back." --Sen 1970

Amartya Sen and Martha Nussbaum suggested that your well-being should not be measured by what you have, but rather by what you can achieve. If there is a book I want and there is a bookstore nearby then I can walk to that store and buy the book. The book is not something I have, but something I can achieve. And achieving implies an action in the graph structure of the world.

We examine a model where the universe consists of worlds, or states, and some states are connected by an action and an agent. Thus $(w, i, f, w')$ says that agent $i$ can go from world $w$ to world $w'$ by performing action $f$. An agent has a value $v(w)$ at each state $w$ and a library $C$ of possible actions. Thus, the agent's ultimate value at $w$ is $max(v(f(w)): f \in C)$. Society may furnish actions, (like a bus line) which enables the agent to supplement her own actions by composing them with actions provided by society. We study the mathematical and social properties of this model.

Speaker: Eric Ramos (Stevens Institute of Technology)

Title: Finding Topology in a (Random) Factory

Abstract: Given your favorite topological space $X$, one may consider the configuration space $Conf_n(X)$ of all n-tuples of points from $X$ that do not overlap. While these spaces were historically only ever thought about when $X$ is a higher dimensional manifold, at around the turn of the century there was a flurry of work considering these spaces in the case where $X$ is one dimensional – i.e. a graph. One of the primary survey papers written at that time on the subject, was “Finding Topology in a Factory: Configuration spaces,” by Robert Ghrist and Aaron Abrams. It was in that paper that a number of beautiful theorems were proven which married the topology of configuration space with the combinatorics of the underlying graph. Since these origins, the study of graph configuration spaces has only grown in a large number of directions. Noticeably missing, however, are any works which consider the statistical or probabilistic properties of configuration spaces on random graphs. It is my hope to study these “random” configuration spaces, and see what kinds of properties they have which mirror the probabilistic combinatorics of random graphs.

Speaker: Pablo Soberon (Baruch College and the Graduate Center, CUNY)

Title: Bisections of Measures with Hyperplane Arrangements

Abstract: Mass partition problems ask how to fairly divide multiple measures in Euclidean space under geometric constraints. A classic example is the ham sandwich theorem, which states that any $d$ absolutely continuous measures on $R^d$ can be simultaneously bisected by a single hyperplane. These problems have traditionally been solved using topological tools, and increasingly complex partition questions have required correspondingly advanced topological machinery.

In recent joint work with Alfredo Hubard, we developed a geometric framework that unifies and generalizes a wide class of mass partition results involving bisections by hyperplane arrangements—recovering, for instance, the ham sandwich theorem—without relying on topology. This raises two natural questions: 

(1) Which other foundational results in the field admit purely geometric proofs? 

(2) Our method requires certain parameters to be odd; can this restriction be removed?

In this talk, we will survey a variety of mass partition problems and present the geometric proof strategy developed in our work.

Speaker: Benjamin Steinberg (City College and the Graduate Center, CUNY)

Title: Markov Chains, Matroids, Hyperplane Arrangements and Semigroups

Abstract: Work of Bidigare, Hanlon, Rockmore, Brown and Diaconis has established connections between combinatorial structures, Markov chains and a class of semigroups called LRBs.  I'll survey some results and ideas in this topic.  My main focus will be on the Tsetlin library and some extensions to matroids, hyperplane arrangements and graphs.

Organizing Committee: Kira Adaricheva, Deepak Bal, Nadia Benakli, Joseph Fehribach Sandra Kingan (co-chair), Melyvn Nathason, Kerry Ojakian, Eric Ramos (co-chair), Pablo Soberón