Seminar

Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem, Part II

Abstract: A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Title: Restricted Intersections and the Sunflower Problem

Abstract: A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. Erdos and Rado showed that a family of sets of size $n$ contains a sunflower if there are more than $n!(r-1)^n$ sets in the family. Alweiss et al. and subsequently Rao improved this bound to $(O(r \log(rn))^n$.

Title: Ramsey Cayley graphs, random graph models, and information theory

Abstract: A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph.

Title: Ramsey degrees, big and small

Abstract: Many of the seminal results in finite Ramsey theory can be phrased by saying that a certain class of finite structures has the Ramsey property, such as the ordinary finite Ramsey theorem (the class of finite linear orders), the dual Ramsey theorem (the class of finite lex-ordered Boolean algebras), the Graham-Leeb-Rothschild theorem (the class of lex-ordered, finite-dimensional vector spaces over a fixed finite field), and the Nesetril-Rodl theorem (the class of finite ordered triangle-free graphs, among many others).

Title: Minors of random representable matroid over finite fields

Abstract: Consider a random n by m matrix A over GF(q) where every column has k nonzero elements, and let M[A] be the matroid represented by A. In the case that q=2, Cooper, Frieze and Pegden (RSA 2019) proved that given a fixed binary matroid N, if k is sufficiently large, and m/n is sufficiently large (both depending on N), then whp. M[A] contains N as a minor. We improve their result by determining the sharp threshold (of m/n) for the appearance of a fixed q-nary matroid N as a minor of M[A], for every k\ge 3, and every prime q. This is joint work with Peter Nelson.

Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem

Abstract:

A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Title: Poset subHopf algebras from growth models in causal set theory and quantum field theory

Abstract: In a story some of you have heard from me before, we get subHopf algebras of the Connes-Kreimer Hopf algebra of rooted trees from certain simple tree classes which correspond to solutions to combinatorial analogues of Dyson-Schwinger equations in quantum field theory.  Another important subHopf algebra of the Connes-Kreimer Hopf algebra is the Connes-Moscovici Hopf algebra which can be viewed as coming from rooted trees grown by adding leaves.

Title: The rank of sparse symmetric matrices over arbitrary fields

Abstract: Consider a sequence of sparse Erdös-Rényi random graphs (G_{n,d/n})_n on n vertices with edge probability d/n. Moreover, we equip the edges of G_{n,d/n} with prescribed non-zero edge weights chosen from an arbitrary field F.

Title: Partial geometric designs, directed strongly regular graphs, and association scheme

Abstract: A partial geometric design with parameters $(v, b, k, r; \alpha, \beta)$ is a tactical configuration $(P, \mathcal{B})$ (with $|P|=v$, $|\mathcal{B}|=b$, every point $p\in P$ belonging to $r$ blocks, and every block $B\in\mathcal{B}$ consisting of $k$ points) satisfying the property:

{for any pair $(p, B)\in P\times \mathcal{B}$, the number of flags $(q, C)$ with $q\in B$ and $C\ni p$ equals to $\alpha  \mbox{ if } p\notin B$ and to $\beta  \mbox{ if } p\in B$.}

Neumaier studied partial geometric designs in detail in his article, ``$t\frac12$-designs," [JCT A {\bf 28}, 226-248 (1980)]. He investigated their connection with strongly-regular graphs and gave various characterizations of partial geometries, bipartite graphs, symmetric 2-designs, and transversal designs in terms of partial geometric designs.

Title: To be announced