Combinatorics-related Open Problems Seminar (CROPS)


An online seminar for presentation of open problems with combinatorial flavor. This includes problems within the field of Mathematics, Theoretical Computer Science, Statistics, etc. Each of the talks at the CROP seminar aims to lead to new collaborations and obtaining of new results.


Organizers: Stoyan Dimitrov (ЕmailТoStoyan {at} gmail.com), Sam Spiro (sas703 {at} scarletmail.rutgers.edu)

Why present at CROPS? Do you have an exciting problem related to Combinatorics? Do you want to find other people to think about it? Don't wait until the next big conference! Contact the organizers and send an abstract to present your problem at CROPS.

Why attend CROPS? Are you looking for new projects, ideas, collaborators, or do you just want to hear about some interesting problems in Combinatorics? If so, you should attend our meetings!

Format, Mailing List and Time:

Format: The total duration of each talk (including questions) is not more than 30 minutes. Most of the talks are 10 to 20 minutes with a few minutes for questions at the end. Each attendee can reach out to the presenter after the talk and the presenter can form a working group with all interested people. A useful resource here might be this file on supercollaboration.

Join our mailing list: Subscribe here. You will receive only one email two days prior to each talk.

Time of the seminar [FALL 2022]: Friday, 12:15pm (Eastern Time, i.e., New York time) ; Usually, we meet bi-weekly.



Schedule FALL SEMESTER 2022:


Talk 1:

Date: Friday, Sept. 23, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Stoyan Dimitrov, Rutgers University

Title: Patterns in special permutation prefixes

Abstract: Most of the permutation patterns literature considers avoidance of various patterns in a set of permutations of given size. However, in many real-life situations, we do not observe the whole permutation at the beginning, but we see its elements one by one. Respectively, we often stop looking at the new elements of the permutation once certain condition holds for the observed prefix (e.g., think of the popular secretary problem). How many of these prefixes do not have an increasing subsequence of length 3? In general, how many prefixes avoid a given permutation pattern? Some computer simulations give promising coincidences with several OEIS sequences for various stopping rules.


Talk 2:

Date: Friday, Oct. 7, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Ishaan Shah, Rutgers University

Title: Chromatic Symmetric Function and a Tree Conjecture

Abstract: In 1995, R.P. Stanley constructed a symmetric function generalization of the chromatic polynomial, X_G, and conjectured that it distinguishes trees. A typical approach to solving this conjecture is to use the coefficients in the power sum basis to reproduce properties such as the degree sequence and the path sequence. If one chooses a connected graph on n vertices, G_n, for each natural n, then {X_{G_n}} form a basis (called a chromatic basis) of the symmetric functions, similar to the so-called power-sum basis. A recent unpublished work discusses a method to generate combinatorial interpretations for the coefficients in these chromatic bases. By understanding these combinatorial interpretations we may hope to get insight on the conjecture that trees can be distinguished. We can also use the chromatic symmetric function to potentially construct new invariant properties of trees.

Talk 3:

Date: Friday, Oct. 21, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Niraj Khare, Carnegie Mellon University in Qatar

Title: Edge Bounds for Graphs and Hypergraphs [link to slides]

Abstract: Abstract: The problem of finding the maximum number of edges a graph can admit without having a subgraph from a forbidden set is well studied. These problems are commonly known as Turan type problems as one of the first such results was due to Turan. Erdos and Gallai considered the problem of finding the maximum number of edges in a graph with n vertices and a given maximal matching size. We share many solved and open problems related to simple graphs. We discuss some structural lemmas for simple graphs and hypergraphs that help us obtain good bounds for the number of edges a graph or a hypergraph can have under certain restrictions. Further we briefly state some open problems and interesting potential edge-bounds for linear hypergraphs.

Talk 4:

Date: Friday, Nov 4, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Peter Kagey, Harvey Mudd College

Title: An Open Problems Collection

Abstract: In graduate school late 2017, I started a catalog of original and independently discovered problems in combinatorics, probability, and geometry. The collection now runs to over 125+ problems, each with a figure, cross-references, and related questions. In this talk, I’ll highlight a few of my favorite problems from this collection and the OEIS sequences and other ideas that came out of them.

Talk 5:

Date: Friday, Nov 18, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Jason O'Neill, California State University, Los Angeles

Title: On l-coverings of the complete k-uniform hypergraph

Abstract: The Graham-Pollak theorem says that in order the partition the edges of the complete graph $K_n$ into complete bipartite graphs, or bicliques, we need at least n-1 bicliques. If we instead allow the edges of the complete graph to appear in at least one and at most l of the bicliques, then Alon showed we need at least roughly $l \cdot n^{1/l}$ such bicliques. A hypergraph extension to the Graham-Pollak theorem (where we want to partition the edges of the k-uniform complete hypergraph into complete k-partite k-uniform hypergraphs) has been extensively explored in the literature.

In this talk, we will explore the analogous problem (to that of Alon), where edges of the complete k-uniform hypergraph may appear in at least one and at most l of the complete k-partite k-uniform hypergraphs. Although the problem statement is relatively straightforward, there has been very little progress on this problem. In particular, the case where k=3 and l=2 is still wide open and no non-trivial bounds have been shown.


Talk 6:

Date: Friday, Dec 2, 2022, 12:15pm (Eastern Time, i.e., New York time)
Zoom Link: https://rutgers.zoom.us/j/98270180477?pwd=VkpsRkg2ZWo4cDU5MTk0bFpzaENSZz09
Passcode: 112515

Speaker: Kiril Bangachev, MIT

Title: Hamiltonicity of Generalized Derangement Graphs [link to slides]

Abstract: In this talk we discuss global properties of anagraphs. Anagraphs are a recently introduced object which generalizes derangement graphs by replacing derangements with "anagrams without fixed letters". Anagrams without fixed letters have been studied at least since the 70s when Even and Gillis related them to Laguerre polynomials.
More concretely, for a finite word w, the anagraph AG(w) is a graph with vertex set all the anagrams of w. Two vertices are adjacent if and only if the corresponding words have different letters at every position. In our work, we determine sufficient and necessary conditions for the connectivity of anagraphs and conjecture that the same conditions also imply Hamiltonicity. This conjecture is based on the Cayley-graph perspective of anagraphs and casts the problem into the broader framework of understanding when Cayley graphs are Hamiltonian.