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 (emailТ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: Usually, we meet bi-weekly on Friday, 12:15pm (Eastern Time, i.e., New York time).



Schedule SPRING SEMESTER 2023:


Talk 7:

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

Speaker: Benjamin Przybocki, Stanford University

Title: Delicate and k-delicate words

Abstract: We study words that barely avoid repetitions, for a couple of senses of "barely". Three kinds of repetition are squares, cubes and overlaps. A square (respectively, cube) is a word of the form XX (respectively, XXX), where X is a nonempty word. An overlap is a word of the form xYxYx, where x is a letter and Y is a possibly empty word. We say a word is squarefree (respectively, cubefree, overlap-free) if none of its factors is a square (respectively, cube or overlap), and in addition such a word is called delicate if changing any one of its letters creates a square (respectively cube or overlap). We classify the lengths of delicate squarefree, overlap-free, and cubefree words over binary and ternary alphabets. Then, we introduce a generalization of delicacy and raise a question about it for further study.

Talk 8:

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

Speaker: Sam Spiro, Rutgers University

Title: Another Open Problems Collection

Abstract: In grad school I started maintaining a small list of open problems of interest on my website. In this talk we'll go through the list and highlight some of my personal favorite problems.

Talk 9:

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

Speaker: Miroslav Marinov, Oxford University (recent graduate)

Title: Pointsets with angles of bounded magnitude

Abstract: Given a real number $\alpha \in [\pi/3, \pi)$ and an integer $d\geq 2$, what is the maximum possible size of a set of points in $\mathbb{R}^d$, such that any angle formed by three of them has size less than or equal to $\alpha$? We shall outline results and connections to combinatorial problems about hypergraphs in some of the regimes for $\alpha$, such as: $\alpha$ close to $\pi/3$ (almost equilateral triangle sets), $\alpha = \pi/2$ (acute sets) and $\alpha$ close to $\pi$ (very obtuse sets). It is also interesting to think about the rate of growth of the maximum size as $\alpha$ increases.

Talk 10:

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

Speaker: Luz Elena Grisales Gómez, MIT (recent graduate)

Title: BFS vs DFS for a random target in plane trees

Abstract: Assume that we are at the root of a random plane tree with n nodes which is not known to us. Our goal is to find a target node and we choose to use either BFS or DFS at the beginning. We investigate the question which of the two algorithms is a better choice for different values of the level of the target node? A few related question will be also proposed.



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.