Online social networks often mirror inequality in real-world networks, from historical prejudice, economic or social factors. Such disparities are often picked up and amplified by algorithms that leverage social data for the purpose of providing recommendations, diffusing information, or forming groups. In this talk, I discuss an overview of my research involving explanations for algorithmic bias in social networks, briefly describing my work in information diffusion, grouping, and general definitions of inequality. Using network models that reproduce inequality seen in online networks, we'll characterize the relationship between pre-existing bias and algorithms in creating inequality, discussing different algorithmic solutions for mitigating bias.

Whitney examined the abstract properties of linear independence and defined matroids via several equivalent axiom systems almost 100 years ago. Matroids have since found many applications, for example in rigidity theory.

By replacing the set difference by the symmetric difference in Whitney's basis axiom for matroids, Bouchet defined Delta-matroids. He described Delta-matroids for maps on surfaces. Using Tutte's combinatorial definition of a map we define a Delta-matroid purely combinatorially and show that it is equivalent to Bouchet's topological definition.

The theory of interacting particle systems is a relatively modern area that has found some unexpected connections to orthogonal polynomials, symmetric functions, and various combinatorial structures. The ASEP (asymmetric simple exclusion process) is one of the most famous such particle models, having a remarkable connection to the Macdonald polynomials P_{\lambda}, which are a family of symmetric functions that have received much attention in algebraic combinatorics. In this talk, we will discuss another particle model called the TAZRP (totally asymmetric zero range process), which has a recently discovered parallel relationship to the modified Macdonald polynomials H_{\lambda}, a combinatorial transformation of P_{\lambda}. We will describe a Markov process on tableaux which makes this relationship explicit. No advanced prior knowledge of probability or symmetric function theory will be assumed. This is joint work with Arvind Ayyer and James Martin.

The classic result of Ramsey states every sufficiently large graph has a large complete graph or large independent set as an induced subgraph. The infinite version of this result states that every infinite graph has an infinite complete graph or an infinite independent set as an induced subgraph. The analogous results for connected graphs state, respectively, that every sufficiently large connected graph has one of a large complete graph, a large star, and a long path as an induced subgraph, and every infinite connected graph has one of an infinite complete graph, an infinite star, and infinite one-way path as an induced subgraph. We prove analogous results, both the finite and the infinite version, for 2-connected graphs.

A (p, q)-coloring of a graph G is an edge-coloring of G (not necessarily proper) in which each p-clique contains edges of at least q distinct colors. We are interested in the function f(n, p, q), first introduced by Erdős and Shelah, which is the minimum number of colors needed for a (p, q)-coloring of the complete graph on n vertices. In 1997, Erdős and Gyárfás initiated the systematic study of this function. Among other results, they gave upper and lower bounds on f(n, p, p) which are still the best known bounds for general p today. In this talk, I will give an overview of this problem and describe recent improvements on the probabilistic upper bound of Erdős and Gyárfás for several small cases of p. This is joint work with Alex Cameron.

Carsten Thomassen and I proved that in any graph G, the number of cycles containing a specified edge as well as all the odd-degree vertices is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Sunichi Toida and where all vertices have odd degree it is Andrew Thomason's generalization of Smith's Theorem.

Kenneth Berman extended Thomason’s Theorem to trees: he used a counting argument to prove that if T is a spanning tree of a graph G where all vertices in G-E(T) have odd degree, there is an even number of spanning trees of G with the same degree as T at each vertex.

I give a common generalization of these results to a parity theorem about (not necessarily spanning) trees.

Andrew Thomason proved his theorem by constructing a graph X(G), his lollipop graph, in which the odd-degree vertices correspond precisely to the things he wants to show there are an even number of, namely the hamiltonian cycles in G containing the specified edge. Christos Papadimitriou calls this approach the polynomial parity argument (PPA). It provides an algorithm for given one of the objects, finding another, by walking in X(G) from one odd-degree vertex to another.

I have extended Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices, and more generally finds a second tree with certain properties. I will discuss these algorithms and some other parity theorems.

Extremal graph theory studies how the amount of edges in a graph can guarantee the existence of a particular substructure, and there are variants that involve edge colorings as well. It is known that any 2-coloring of the edges of a large enough complete graph with enough edges in each color class contains at least one of two patterns, either a colored K_{2t} where one color class induces a K_t or a colored K_{2t} where one color class induces two disjoint K_{t}s. This result has given birth to many interesting problems involving balanceability (which seeks structures with equal proportions of color) and omnitonality (which seeks structures with all possible proportions of color). In this talk, we will discuss some results concerning balanceability and the unavoidable pattern found when we color the edges of a large enough complete bipartite graph.

Convexity is one of the useful geometric properties of digital sets in digital image processing. There are various applications which require deforming digital convex sets while preserving their convexity. In this talk, I will consider the contraction of such digital sets by removing digital and adding points one by one. For this aim, we use some tools of combinatorics on words to detect a set of removable and addable points and to define such convexity-preserving contraction of a digital set as an operation of re-writing its boundary word.

A De Bruijn cycle is a cyclic sequence of symbols that contains each word of length n exactly once. A universal partial cycle, or upcycle, covers each word of length n exactly once, even more compactly, using a "do not know" symbol that covers every letter of the alphabet. Upcycles have highly constrained structure and seem to be rare. Previously it was not known whether any upcycles existed for n > 4. We present several examples of upcycles with n = 8. We then present novel approaches to constructing new upcycles from old ones, so that each of these new examples generates an infinite family of upcycles. At the same time, we find that upcycles are more structurally constrained than previously known and satisfy certain pseudorandomness properties, and we prove new nonexistence results.

This talk is based on joint work with Bennet Goeckner, Corbin Groothuis, Cyrus Hettle, Brian Kell, Pamela Kirkpatrick, and Ryan Solava and joint work with Dylan Fillmore, Bennet Goeckner, Jasmine Martin, and Daniel McGinnis.

People who volunteer as living kidney donors are often incompatible with their intended recipients. Kidney paired donation matches one patient and his or her incompatible donor with another pair in the same situation for an exchange. We represent patient-donor pairs be the vertices of a directed graph G, with edges connecting pairs if the donor of the source is compatible with the recipient of the sink. To find the best kidney exchanges, we maximize the sum of edge weights on disjoint cycles. I will first review various exponential-sized and polynomial-sized integer programming formulations proposed for this problem, and give an overview of integer programming solution methods to suggest why some formulations are more tractable than others.

Because a maximum edge-weight matching might not have the maximum number of possible transplants (cardinality), there is a risk of an unpredictable trade-off between quality and quantity of paired donations. The number of paired donations is within a multiplicative factor of the maximum possible donations, where the factor depends on the edge weighting. We design an edge weighting of G which guarantees that every matching with maximum weight also has maximum cardinality, and also maximizes the number of transplants for an exceptional subset of recipients, while favoring immunologic concordance.

We will start with an introduction to webs, standard Young tableau promotion, and the relationship between web rotation and tableau promotion. We will then discuss increasing tableaux---a K-theoretic analogue of SYT---and K-promotion. A big open question in this area deals with the order of K-promotion on increasing tableaux. We will talk about results in the 3-row case (in joint work with O. Pechenik) as well as current efforts to relate this problem to web promotion (joint with O. Pechenik, J. Striker, and J. Tymoczko).

In this talk we mixed two different areas on combinatorics. Specifically, we take some results on finite geometries and combinatorial designs to solve classical problems on graph theory.

The first problem is related to extremal graphs and specifically to the construction of Moore graphs and cages. Here, we study this problem but on Mixed Graphs, where a Mixed regular graph is a (z, r)-graph, z-regular by arcs and r-regular by edges, a (z, r; d)-mixed Moore graph is a mixed graph with fixed diameter d and maximum order whereas a [z, r; g]-mixed cage is a mixed graph with fixed girth g and minimum order. In this talk we use the finite geometries and their incidence graphs to construct both mixed Moore graphs and cages.

The second problem studies complete colorations in circulant graphs. A complete k-vertex-coloring of a graph G is a vertex-coloring of G using k colors such that for every pair of colors there is at least two incident vertices in G colored with this pair of colors. The chromatic χ(G) and achromatic α(G) numbers of G are the smallest and the largest number of colors in a complete proper k-vertex-coloring of G, therefore χ(G) ≤ α(G). If we coloring the edges, instead the vertices of a graph G, the analogous parameter is called the achromatic index , and denoted by α _0 (G). In this talk, we determine the achromatic index for circulant graphs of order q 2 + q + 1 using projective planes.