titles and Abstracts

In this talk, I will discuss some new results on intersection graphs of pseudo-segments in the plane and their applications in graph drawing.  These results are joint work with Jacob Fox and Janos Pach.

It is an important problem in algebraic combinatorics to deduce the Schur function expansion of a symmetric function whose expansion in terms of the fundamental quasisymmetric function is known. For example, formulas are known for the fundamental expansion of a Macdonald symmetric function and for the plethysm of two Schur functions, while the Schur expansions of these expressions are still elusive. Egge, Loehr and Warrington provided a method to obtain the Schur expansion from the fundamental expansion by replacing each quasisymmetric function by a Schur function (not necessarily indexed by a partition) and using straightening rules to obtain the Schur expansion. Here we provide a new method that only involves the coefficients of the quasisymmetric functions indexed by partitions and the quasi-Kostka matrix. As an application, we identify the lexicographically largest term in the Schur expansion of the plethysm of two Schur functions. We provide the Schur expansion of sw[sh](x,y) for w=2,3,4 using novel symmetric chain decompositions of Young's lattice for partitions in a w×h box. For w=4, this is first known combinatorial expression for the coefficient of sλ in sw[sh] for two-row partitions λ, and for w=3 the combinatorial expression is new.

This is based on joint work with Rosa Orellana, Franco Saliola and Mike Zabrocki (arXiv:2404.04512).

A "frieze" is an infinite strip of numbers satisfying certain determinantal identities, or any one of several generalizations of this idea. I will give an introduction to friezes whose shape is determined by a Dynkin diagram (motivated by their exceptional properties as well as connections to representation theory and cluster algebras). One of the simplest questions was open until recently: are there finitely many such friezes? Time permitting, I will describe two proofs of finiteness, and on-going work into enumerating them.

Expander graphs are perhaps one of the most widely useful classes of graphs ever considered. In this talk, we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlós and Szemerédi around 30 years ago. They have found many remarkable applications ever since. In particular, we will focus on certain robustness conditions one may impose on sublinear expanders and some applications of this idea, which include:

- recent progress on the classical Erdős-Gallai cycle decomposition conjecture,

- an essentially tight answer to the classical Erdős unit distance problem for "most" real normed spaces and

- an asymptotic solution to the rainbow Turan problem for cycles, raised by Keevash, Mubayi, Sudakov and Verstraete, with surprising applications in discrete geometry, coding theory and additive number theory.

We present a randomized sequential algorithm that, given $\epsilon > 0$, outputs a proper $(1+\epsilon)\Delta$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $\Delta \geq 1/\epsilon$ in $O(m/\epsilon^9)$ time. For constant $\epsilon$, this is the first linear-time algorithm for this problem covering the full range of $\Delta$. Previously, an algorithm with runtime $O(m \, \log(1/\epsilon)/\epsilon^2)$ was given by Bhattacharya, Costa, Panski, and Solomon under the assumption that $\Delta \geq (\log n/\epsilon)^{\poly(1/\epsilon)}$, and removing this lower bound on $\Delta$ was mentioned by them as a challenging open problem. Furthermore, until now no linear-time algorithm for all $\Delta$ was known even for edge-coloring with $2\Delta - 1$ colors (which is the “greedy” bound for edge-coloring). This is based on joint work with Anton Bernshteyn.

We present a common refinement of the multigraded Hilbert series, the Cauchy identity, and the Littlewood-Richardson rule for computing the Levi characters of “bicrystalline” algebraic varieties. The proof introduces a “filtered” generalization of the Robinson-Schensted-Knuth correspondence. This is joint work with Ada Stelzer and Alexander Yong.

Matrix Schubert varieties [Fulton '92] are closed under the Levi group action of block-diagonal matrix multiplication, inducing a decomposition of their coordinate rings into irreducible representations. When the Levi group is a torus, [Knutson-Miller '04] gives a combinatorial rule for the multiplicity of the irreducibles in these coordinate rings. We give a combinatorial rule for the general Levi case, a common refinement of the multigraded Hilbert series, the Cauchy identity, and the Littlewood-Richardson rule. Our arguments apply to a broader class of "bicrystalline" varieties, which we define using operators of [Kashiwara '95] and [Danilov-Koshevoi '05, van Leeuwen '06]. The proof introduces a "filtered" generalization of the Robinson-Schensted-Knuth correspondence. This is joint work with Abigail Price and Alexander Yong.

A graph $G$ is \textit{$k$-locally sparse} if for each vertex $v \in V(G)$, the subgraph induced by its neighborhood contains at most $k$ edges. Alon, Krivelevich, and Sudakov showed that for $f > 0$ if a graph $G$ of maximum degree $\Delta$ is $\Delta^2/f$-locally-sparse, then $\chi(G) = O\left(\Delta/\log f\right)$. We introduce a more general notion of local sparsity by defining graphs $G$ to be \textit{$(k, F)$-locally-sparse} for some graph $F$ if for each vertex $v \in V(G)$ the subgraph induced by the neighborhood of $v$ contains at most $k$ copies of $F$. Employing the R\"{o}dl nibble method, we prove the following generalization of the above result: for every bipartite graph $F$, if $G$ is $(k, F)$-locally-sparse, then $\chi(G) = O\left( \Delta /\log\left(\Delta k^{-1/|V(F)|}\right)\right)$. This improves upon results of Davies, Kang, Pirot, and Sereni who consider the case when $F$ is a path. Our results also recover the best known bound on $\chi(G)$ when $G$ is $K_{1, t, t}$-free for $t \geq 4$, and hold for list and correspondence coloring in the more general so-called ``color-degree'' setting. This is joint work with James Anderson and Abhishek Dhawan.  

We study how far one can deviate from optimal behavior when drawing a planar graph on a plane. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a \textit{plane-saturated subgraph} if adding any edge (possibly with a new vertex) to $H$ would either violate planarity or make the resulting graph no longer a subgraph of $G$. We define the \textit{plane-saturation ratio}, $\psr(G)$, as the minimum value of $\frac{e(H)}{e(G)}$ for a plane-saturated subgraph $H\subseteq G$ and investigate how small $\psr(G)$ can be. While there exist planar graphs where $\psr(G)$ is arbitrarily close to $0$, we show that for all twin-free planar graphs, $\psr(G)>1/16$, and that there exist twin-free planar graphs where $\psr(G)$ is arbitrarily close to $1/16$. 

"A rooted chord diagram is a set of ordered pairs of the form $(a_i,b_i)$ such that $\{a_1,b_1, a_2, b_2, \dots, a_n,b_n\} = \{1,2, \dots, 2n\}$ and $a_i < b_i$ for each $1 \leq i \leq n$. The pair $(a_i,b_i)$ is the $i^{th}$ chord in the chord diagram. The chord $a_1=1$ is the \emph{root chord}. A binary tubing, $\tau$ of a rooted tree is a set of tubes, where tubes are sets of vertices, and every tube is made up of at least two disjoint subtubes. The class of plane rooted trees with $n$ vertices and tubing $\tau$ are in bijection with the class of chord diagrams with $n$ chords. Re-rooting is an operation on a plane rooted tree where the underlying graph structure and the planar property of the tree is preserved, but a different vertex is taken to be the root; tubes of the tree are also preserved. When a tree is re-rooted, the corresponding chord diagram changes. In this talk I will describe an algorithm for determining the chord diagrams corresponding to rooted trees after the tree has been re-rooted."

Consider the (infinite-dimensional) vector space whose basis vectors are indexed by integer partitions. We will discuss two sources of linear operators on this vector space. The first source, solvable lattice models, are ice-like rectangular grids that originated in statistical physics, and which satisfy the famous Yang-Baxter equation. The second source, the boson-fermion correspondence, has connections to soliton solutions of the KP hierarchy. We will discuss the intersection of these two approaches, which has applications to symmetric functions.

"Following work of Peled, Samotij, and Yehudayoff, we study uniform random integer-valued Lipschitz functions on d-regular spectral expanders. While such a graph may be locally tree-like, encouraging the function to take a wide range of values, we show that the global connectivity properties of these expanders force a typical Lipschitz function to be quite flat, with its range being logarithmic in the diameter of the graph with high probability. Our proof techniques include a combination of Sapozhenko's graph containers and entropy methods."

A set family F on ground set [n] is maximal k-wise intersecting if every collection of at most k sets in F has non-empty intersection, and no other set can be added to F while maintaining this property. In 1974, Erdős and Kleitman asked for the minimum size of a maximal k-wise intersecting family. We answer their question for k=3 and sufficiently large n by showing that the unique minimum family is obtained by partitioning [n] into two sets A and B with almost equal sizes and taking the family consisting of all the proper supersets of A and of B. This is a joint work with József Balogh, Kevin Hendrey, Ben Lund, Haoran Luo, Casey Tompkins and Tuan Tran.

The up-down walk is a Markov chain on subsets of a fixed size of some ground set.  We discuss the up-down walk for matchings of a fixed submaximal size on any graph G.  We show that the walk mixes in polynomial time using the method of canonical paths and explain obstructions to getting O(n log n) mixing time and whether this can be expected.

In 1957, Hadwiger provided a necessary and sufficient condition for a family of convex sets in the plane to have a line transversal, namely, a line that intersects each set. This was eventually generalized to families of convex sets in higher dimensions in a series of papers among the authors Goodman, Pollack, and Wenger. In this talk, we present a complex analogue of the Goodman-Pollack-Wenger theorem.

"Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any edge coloring of a large enough $K_n$ using $2$ colors such that there is a sufficient amount of edges in each color. In 2019, Caro, Hansberg and Montejano defined amoeba graphs in a pure combinatorical setting. They discovered important properties but could not prove them formally using only combinatorics, so they provided an equivalent definition that employed group theory, facilitating their proofs greatly and allowing them to use algebraic techniques.\\

We label the vertices in our graphs. 

An edge-replacement in $G$ means to take away an edge and place it in an available spot. If the resulting graph is isomorphic to the original graph, we say that the edge-replacement is \emph{feasible}. Notice that every feasible edge-replacement yields a set of permutations of the labels in $G$. The set of all permutations associated with all feasible edge-replacements in $G$ generates the group $\fer(G)$. A graph $G$ of order $n$ is a \emph{local amoeba} if $\fer(G) \cong S_n$ and a \emph{global amoeba} if $\fer(G\cup tK_1)\cong S_{n+t}$, for a large enough $t$. An interesting problem is to find local and/or global amoebas. One might think they are hard to find, and they generally are.  However, in this talk we will go over a recursive construction of infinite families of local amoebas that answers an open problem posed by Caro, Hansberg and Montejano. We also give the minimum number of feasible edge-replacements necessary to prove that a Fibonacci-type tree is a local amoeba."

"A system of linear equations L is common over F_p if, as n->infty, any 2-coloring of F_p^n gives asymptotically at least as many monochromatic solutions to L as a random 2-coloring.

The notion of common linear systems is analogous to that of common graphs, i.e., graphs whose monochromatic density in 2-edge-coloring of cliques is asymptotically minimized by the random coloring. Saad and Wolf initiated a systematic study on identifying common linear systems, built upon the earlier work of Cameron-Cilleruelo-Serra. When L is a single equation, Fox-Pham-Zhao gave a complete characterization of common linear equations. When L consists of two equations, Kamčev-Liebenau-Morrison showed that irredundant 2*4 linear systems are always uncommon. In joint work with Anqi Li and Yufei Zhao, (1) we determine commonness of all 2*5 linear systems up to a small number of cases, and (2) we show that all 2*k linear systems with k even and girth (minimum number of nonzero coefficients of a nonzero equation spanned by the system) k-1 are uncommon, answering a question of Kamčev-Liebenau-Morrison."

Cluster algebras are a type of recursively generated commutative ring whose generators (called cluster variables) appear in fixed-size distinguished subsets (called clusters). A particularly approachable type of cluster algebra is that of surface type, which can be modeled using triangulated surfaces. In joint work with Esther Banaian and Wonwoo Kang, we use a combinatorial expansion formula via order ideals of posets to give explicit skein relations for elements of cluster algebras arising from punctured surfaces. (This talk will assume no prior familiarity with cluster algebras)

"We consider the extremal problem of counting the number of copies of a fixed graph in another larger graph in the ordered setting. Among ordered n-vertex graphs with m edges, we determine the maximum and minimum number of copies of a k-edge star whose nonleaf vertex is minimum among all vertices of the star. The constructions achieving the maximum and minimum are both quasi-stars, but with opposite vertex order. This talk is based on joint work with Laura Eslava, Adriana Hansberg and Tonatiuh Matos."

All planar graphs have a straight-line drawing in a two-dimensional grid. All graphs have a straight-line drawing in a three-dimensional grid. For many families of graphs, determining the smallest possible volume or aspect ratio of a grid that the family can be drawn is an open question. Using probabilistic methods, we obtain grid-drawings of graphs without crossings with low volume and small aspect ratio. We show that every $D$-degenerate graph on $n$ vertices can be drawn in $[m]^3$ where $m = O(D^{5/3} n^{1/3}\log^{4/3}n)$. This resolves a long-standing problem of Pach, Thiele, and T\'oth up to logarithmic factors. \emph{Joint work with J\'ozsef Balogh.}

Ryser's conjecture is typically stated as a problem on hypergraphs. For an r-partite hypergraph H, let \tau(H) denote the size of a minimum vertex cover and \nu(H) the size of a maximum matching. Ryser's conjecture proposes that \tau(H) \leq (r-1)\nu(H). Gyarfas noted that Ryser's conjecture is equivalent to considering monochromatic coverings of edge-colored graphs. For graph G, tc_r(G) is the minimum number of monochromatic components whose union contains V(G) for any r-edge-coloring of G, and \alpha(G) is the independence number. Ryser’s conjecture can be reformulated as tc_r(G) \leq (r-1)\alpha(G). This reformulation allows for some interesting variations. We present known results on Ryser’s conjecture and its generalizations, including considering a variation in which we cover the vertex set of a graph with monochromatic subgraphs of bounded diameter. This is joint work with DeBiasio, Kamel, and Sheats and English, Mattes, and Phillips.

"The Deligne-Mumford compactification, $\overline{M_{0,n}}$, of the moduli space of $n$ distinct ordered points on $\mathbb{P}^1$, has many well understood geometric and topological properties. For example, it is a smooth projective variety over its base field. Many interesting properties are known for the manifold $\overline{M_{0,n}}(\mathbb{R})$ of real points of this variety. In particular, its fundamental group, $\pi_1(\overline{M_{0,n}}(\mathbb{R}))$, is related, via a short exact sequence, to another group known as the cactus group. Henriques and Kamnitzer gave an elegant combinatorial presentation of this cactus group.\\ 

        In 2003, Hassett constructed a weighted variant of $\overline{M_{0,n}}(\mathbb{R})$: For each of the $n$ labels, we assign a weight between 0 and 1; points can coincide if the sum of their weights does not exceed one. We seek combinatorial presentations for the fundamental groups of Hassett spaces with certain restrictions on the weights. 

        In particular, we express the Hassett space as a blow-down of $\overline{M_{0,n}}$ and modify the cactus group to produce an analogous short exact sequence. The relations of this modified cactus group involves extensions to the braid relations in $S_n$. To establish the sufficiency of such relations, we consider a certain cell decomposition of these Hassett spaces, which are indexed by ordered planar trees."

"Denote by C_ℓ^- the 3-uniform hypergraph obtained by removing one hyperedge from the tight cycle on ℓ vertices. It is conjectured that the Turán density of C_5^- is 1/4. We make progress toward this conjecture by proving that the Turán density of C_ℓ^- is 1/4, for every sufficiently large ℓ not divisible by 3. One of the main ingredients of our proof is a forbidden-subhypergraph characterization of the hypergraphs, for which there exists a tournament on the same vertex set such that every hyperedge is a cyclic triangle in this tournament.

This is joint work with József Balogh."

In 2003, Bohman, Frieze, and Martin proved that for every d>0, there exists C such that every n-vertex graph G with minimum degree dn contains a spanning cycle when Cn random edges are added, with probability tending to 1 as n tends to infinity. This result fits between two classical theorems: Dirac's theorem, which states that minimum degree n/2 is necessary and sufficient to ensure a spanning cycle, and a series of theorems which state that random graphs with Cn log(n) edges have spanning cycles with high probability (for more precise choices of C). Bohman, Frieze, and Martin also prove a digraph analogue of their result, where given a minimum out- and indegree condition, they find a spanning cycle with all the edges oriented the same way around the cycle. We generalize this digraph result to find cycles of every length and orientation, simultaneously, with high probability. This is joint work with József Balogh, Robert A. Krueger, Simón Piga, and Andrew Treglown.

By inventing the notion of honeycombs, A. Knutson and T. Tao proved the saturation conjecture for Littlewood-Richardson coefficients. The Newell-Littlewood numbers are a generalization of the Littlewood-Richardson coefficients. By introducing honeycombs on a Möbius strip, I will discuss about the saturation conjecture for Newell-Littlewood numbers posed by S. Gao, G. Orelowitz and A. Yong.

Defective coloring (also  known as relaxed or improper coloring) is a generalization of proper coloring defined as follows: for $d \in \mathbb{N}$, a coloring of a graph is \textit{$d$-defective} if every vertex is colored the same as at most $d$ many of its neighbors. We consider defective colorings of planar graphs in the context of correspondence coloring, demonstrating several results that hold for defective list coloring do not generalize to defective correspondence coloring. On the other hand, we provide a construction of a planar graph that is $1$-defective $3$-correspondable but not $4$-correspondable, thereby extending a recent result of Ma, Xu, and Zhu from list coloring to correspondence coloring. We also investigate defective correspondence coloring for outerplanar graphs, completely characterizing the tuples $(d,k)$ for which an outerplanar graph is $d$-defective $k$-correspondable.

In this talk, we consider the skein algebra (or cluster algebra) of an oriented marked surface with boundary. Each triangulation of the surface determines an algebraic torus in the corresponding variety, and in some cases these tori collectively cover the variety. In other cases, there are points not contained in any algebraic torus, which we call deep points. In joint work with Greg Muller, we have classified the deep points of skein algebras of unpunctured marked surfaces. We will discuss this classification, beginning with convex polygons and then extending those same ideas to other unpunctured surfaces. If time permits, we will then discuss work in progress regarding marked surfaces with punctures.

Graph burning is a discrete-time process that models the spread of influence in a network. Vertices are in one of two states: either burning or unburned. In each round, a burning vertex causes all of its neighbors to become burning and then a previously unburned vertex is chosen whose state is changed to burning. Previous work has focused on bounding the number of turns necessary to burn an $n$-vertex graph. We introduce a variation of the graph burning process that incorporates an adversarial game played on a nested, growing sequence of trees. Two players, Arsonist and Builder, play in turns: Builder adds unburned vertices to create a larger tree, then burning vertices spread fire to their neighbors, and finally Arsonist `lights' a new fire on an unburned vertex. This process repeats forever. Arsonist is said to win if the limiting fraction of burned vertices tends to 1, while the Builder is said to win if this fraction is bounded away from 1. We consider how the number of vertices granted to Builder each turn affects the optimal strategies for each player.

"List packing is a relatively new notion that was first suggested by Alon, Fellows, and Hare in 1996, but the suggestion was not formally embraced until a recent paper of Cambie, Cames van Batenburg, Davies, and Kang in 2021.  Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study the existence of such a packing of list colorings.  In this talk we consider counting these packings. 

We define the list packing function of a graph G as the guaranteed number of proper L-packings of a prescribed size over all list assignments L that assign the same number of colors to each vertex of G.  In the case the prescribed size is one, the list packing function of G is equal to its list color function which is the well-studied analogue of its chromatic polynomial in the context of list coloring.  Inspired by the well-known behavior of list color functions and chromatic polynomials, we consider the list packing function of a graph in comparison to its classical coloring counterpart.  This leads to a generalization of a recent theorem of Dong and Zhang (2023), which improved results going back to Donner (1992), about when the list color function of a graph equals its chromatic polynomial. Further, we show how a polynomial method can be used to generalize bounds on the list packing number of sparse graphs to exponential lower bounds on the corresponding list packing functions.

This is joint work with Hemanshu Kaul."

"In 2017, Davis and Sagan found that a pattern-avoiding Birkhoff subpolytope and an order polytope have the same normalized volume. They ask whether the two polytopes are unimodularly equivalent. We give an affirmative answer to a generalization of this question. 

For each Coxeter element c in the symmetric group, we define a pattern-avoiding Birkhoff subpolytope, and an order polytope of the heap poset of the c-sorting word of the longest permutation. We show the two polytopes are unimodularly equivalent. As a consequence, we show the normalized volume of the pattern-avoiding Birkhoff subpolytope is equal to the number of the longest chains in a corresponding Cambrian lattice. In particular, when c = s_1s_2…s_{n-1}, this resolves the question by Davis and Sagan.

This talk is based on ongoing joint work with E. Banaian, S. Chepuri and E. Gunawan."

Matroids give rise to several natural constructions of polytopes. Oriented matroids, similarly, yield many of these same constructions. We examine polytopes that arise from the signed circuits of an oriented matroid. We give the dimensions of such polytopes arising from graphical oriented matroids and their duals. Moreover, we consider polytopes constructed from cocircuits of oriented matroids generated by the positive roots in any type A root system. We give explicit descriptions of these polytope and determine the Ehrhart series. These type A polytopes are graphic zonotopes, are polar duals of symmetric edge polytopes, and also make an appearance in Stapledon’s paper introducing Equivariant Ehrhart Theory. This work is joint with Laura Escobar.

In previous work, Auli and Elizalde characterized generalized Wilf equivalences among all 75 consecutive patterns of length 4, proving some with direct bijections and some via inclusion-exclusion arguments. For those proved by inclusion-exclusion, we derive some new bijective proofs, and show a stronger relation among some consecutive patterns.

"We will show that if $G$ is a $2$-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $\frac{5n + n_2}{4} - 1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $\frac{5n + n_2}{4}  - 1$ (respectively, $\frac{5n}{4} - 2$). We will outline how a quadratic-time algorithm can be obtained from the proof, thus yielding a $\frac{5}{4}$-approximation algorithm for graphic TSP of simple cubic graphs, improving upon the prior best guarantee of $\frac{9}{7}$.

Joint work with Youngho Yoo and Xingxing Yu."

Ahlswede and Cai proved that if a simple graph has nested solutions under the edge-isoperimetric problems, and the lexicographic order produces nested solutions for its second cartesian power, then the lexicographic order produces nested solutions for any finite cartesian power. In this talk I will present a generalization of this result that just assumes an existence of nested solutions, and does not require that the lexicographic order is used. That is, under very general assumptions, if a graph and its second cartesian power have nested solutions, then so does any finite cartesian power. Harper asked if this is true without any restriction. I also conjecture that this is true and will present some ideas on how to attack this conjecture.

"A deterministic finite automaton (DFA) is a directed graph G of regular out-degree d, along with d labels which are assigned bijectively to the d arcs outgoing from each vertex. A synchronizing sequence in G is a sequence S of labels such that by starting at any vertex of G and following the labels of S, one always arrives at the same vertex. Černý conjectured that if G has n vertices and a synchronizing sequence, then the shortest synchronizing sequence of G has length at most (n-1)^2.

In this talk, we present a general strategy, which we call the cornering strategy, for generating short synchronizing words in well-structured DFAs. We also show that a DFA is synchronizable if and only if this strategy can be applied. Using the cornering strategy, we prove that all DFAs consisting of n points in real space with bidirectional connected edge sets whose arc labels are given by difference vectors have a synchronizing sequence. Furthermore, we give sufficient conditions for such a DFA to have a synchronizing word of length at most (n-1)^2. 

This talk is joint work with Alexander Clow and Ladislav Stacho."

"We say a finite poset $P$ is a tree poset if its Hasse diagram $H(P)$ is a tree. Let $h(P)$ be the length of the largest chain contained in $P$. In this talk, we will show that when $P$ is a tree poset, the number of $P$-free subfamilies of $2^{[n]}$ is $2^{(h(P)-1+o(1))\binom{n}{n/2}}$. The proof uses a generalization of a Theorem by Boris Bukh [The Electronic Journal of Combinatorics, 2009] and a variation of the standard graph container algorithm."

Every positive rational number has representations as Egyptian fractions with arbitrarily many terms and arbitrarily large denominators. In this talk, we consider Egyptian fraction representations in Function field setting \mathbb{F}_{q}(t). We show that the unit fraction representation exists for every rational function $R(t)= \frac{F(t)}{G(t)} $ after two necessary restrictions. We also construct unit fraction representations for rational functions with many terms by finding large zero-sum sets.

Given an $n$-vertex digraph $D$ and a labeling $\sigma:V(D)\to [n]$, we say that an arc $u\to v$ of $D$ is a descent of $\sigma$ if $\sigma(u)>\sigma(v)$.   Foata and Zeilberger introduced a generating function $A_D(t)$ for labelings of $D$ weighted by descents, which simultaneously generalizes both Euleraian polynomials and Mahonian polynomials.  Motivated by work of Kalai, we look at problems related to $-1$ evaluations of $A_D(t)$.  In particular, we give a combinatorial interpretation of $|A_D(-1)|$ in terms of ``generalized alternating permutations'' whenever the underlying graph of $D$ is bipartite.

"The extremal number of the graph $F$, denoted $\mathrm{ex}(n,F)$, is the maximum number of edges in an $F$-free graph on $n$ vertices. The inverse rational exponent conjecture (perhaps first posed by Erd\H{o}s and Simonovits in '81) postulates that for each rational number $r\in [1,2]$, there exists some graph $F$ such that

\[

\mathrm{ex}(n,F)=\Theta(n^r).

\]

Recently,  Bukh and Conlon proved a slightly weaker version of this conjecture - if one allows for finite families of forbidden graphs, then such a family does exist for each rational $r$.

We will show that a generalization of this conjecture also holds. Given two graphs $F$ and $H$, the generalized extremal number $\mathrm{ex}(n,H,F)$ is the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices (note that $\mathrm{ex}(n,F)=\mathrm{ex}(n,K_2,F)$). We will explore which rational exponents are realizable for some different graphs $H$.

This is joint work with Anastasia Halfpap and Bob Krueger."

I will discuss how Young tableaux arise from the Plucker map. Influential work of Hodge from the 1940s led the way in using Grobner bases to combinatorially study the Grassmannian. In the past decade, the work of Knutson-Lam-Speyer, and more recently Galashin-Lam, has brought to the fore the significance of positroid subvarieties in the Grassmannian. I will explain how to use Young tableaux to understand these subvarieties and thereby how to connect promotion on Young tableaux with the cyclic symmetry of positroid varieties. This is based on joint work with Ayah Almousa and Daoji Huang, see arxiv.org/abs/2309.15384.

We study the generalized Ramsey-Tur\'an function $RT(n,K_q,K_p,o(n))$, the maximum number of copies of $K_q$ in an $n$-vertex $K_p$-free graph with independence number sublinear in $n$. The case $q=2$ was resolved by Erd\H os, S\'os, Bollob\'as, Hajnal, and Szemer\'edi in the 1980s. More recently, Balogh, Liu, and Sharifzadeh resolved the $q=3$ and $p=q+2$ cases. We extend these results to the cases of $q=4$ and $q=5$, as well the general cases $p\geq 5q$ and $q+3\leq p\leq q+5$, along the way disproving a conjecture of Balogh, Liu, and Sharifzadeh. Joint work with J\'ozsef Balogh and Cory Palmer.

For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. We survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.

 In this talk, I will introduce the Lindstrom-Gessel-Viennot theorem and our extension, then present some applications. The Lindstrom-Gessel-Viennot theorem is a powerful and elegant result with numerous applications in different contexts, such as enumerating various types of plane partitions, semi-standard Young tableaux, and providing combinatorial proof of the Jacobi-Trudi type identities and some determinant formulas. This theorem gives a determinant formula for the signed enumeration of families of non-intersecting paths with any given starting and ending points (according to the connection type). Our result provides the straight count of these families, expressing it as a determinant whose entries are signed counts of lattice paths with given starting and ending points.

Counting the number of acyclic orientations is one of interesting problems in graph theory. In this talk, I will introduce some prior works on finding the number of a acyclic orientations in random graphs, as well as our improvement. Joint work with Jeong-Han Kim.

Motivated by Hadwiger's conjecture, we study graphs $H$ for which every graph with minimum degree at least $|V(H)|-1$ contains $H$ as a minor. We prove that a large class of apex-outerplanar graphs satisfies this property. Our result gives the first examples of such graphs whose vertex cover numbers are significantly larger than half of the number of its vertices, and our proof can be adapted to directed graphs to obtain new results on subdivisions of orientations of cycles and $K_4$. Joint work with Chun-Hung Liu.

A (vertex) separator of a planar graph G(V, E) is a subset S of V such that V \ S can be partitioned into V_0, V_1 that are disconnected from each other and of balanced sizes (up to a constant factor). General planar graphs admit separators of size O(\sqrt{n}), which imply divide-and-conquer strategies for shortest paths, max flow, triangulation, etc. Bi-connected planar graphs admit connected (cycle) separators of size O(\sqrt{n}), which imply faster algorithms for shortest paths, max flow, girth, etc. 

We construct, for a general planar graph G and any parameter r \in (1, \sqrt{n}], a separator consisting of at most two paths of length O(r\sqrt{n}) and at most O(\sqrt{n}/r) additional vertices. The separator can be applied recursively to decompose G into constant size regions such that the number of components of the separator (excluding the additional vertices) is O(log n). The connectedness allows us to use bounded-difference min-plus product to obtain a faster algorithm for the girth of 2D segment intersection graphs.

Schubert polynomials represent a basis for the cohomology of the complete flag variety and thus play a central role in geometry and combinatorics. In this context, Schubert polynomials are generating functions over various combinatorial objects, such as rc-graphs or reduced pipe dreams. By restricting Bergeron and Billey’s chute moves on rc-graphs, we define a Demazure crystal structure on the monomials of a Schubert polynomial. As a consequence, we provide a method for decomposing Schubert polynomials as sums of key polynomials, complementing related work of Assaf and Schilling via reduced factorizations with cutoff, as well as Lenart’s coplactic operators on biwords.

"A proper vertex coloring of a graph is equitable if the sizes of all color classes differ by at most $1$. For a list assignment $L$ of $r$ colors to each vertex of an $n$-vertex graph $G$, an equitable $L$-coloring of $G$ is a proper coloring of vertices of $G$ from their lists such that no color is used more than $\lceil n/r\rceil$ times. A graph is equitably $r$-choosable if it has an equitable $L$-coloring for every $r$-list assignment $L$. A graph is $(a, b)$-sparse if for every $A\subseteq V(G)$, the number of edges in the subgraph $G[A]$ of $G$ induced by $A$ is at most $a|A|+b$.

Our first result is that every $(7/6, 1/3)$-sparse graph with minimum degree at least $2$ is equitably $3$-colorable and equitably $3$-choosable. Our second result is that every $(5/4, 1/2)$-sparse graph with minimum degree at least $2$ is equitably $k$-colorable and equitably $k$-choosable for every $k\ge 4$. We also introduce the notion of strongly equitable list coloring as a combination of equitable coloring and equitable list coloring.

This talk is based on joint work with Alexandr Kostochka and Hal Kierstead."