Combinatorics Seminar

• Dec 5, Cliff Gaddy, A Variant of the Hypergraph Removal Lemma
  in his similarly titled paper, Terence Tao gives a relatively short and self-contained proof of a strengthening of the hypergraph removal lemma by rephrasing the problem in a probabilistic framework. This lemma implies results of Szemerédi on arithmetic progressions as well as other generalizations on arithmetic progressions. As a special case, it also implies the Triangle Removal Lemma, tripartite graph version, which allows one to approximate a tripartite graph with bounded number of triangles by a triangle-free tripartite graph. In my talk, I will give an overview of this paper and the motivations behind it.
• Nov 14 Travis Johnston Turán Problems on Non-uniform Hypergraphs
  Using the Lubell function, we are able to generalize the notion of Turán density for non-uniform hypergraphs. We will give proofs of some generalizations of classical results, including: the supersaturation lemma and the fact that blowing-up doesn't change the Turán density. We also completely characterize the Turán density for certain families of hypergraphs. The talk will include a lot of examples - with pictures - and proofs of some of the main theorems. This is joint work with Linyuan "Lincoln" Lu.
• Nov 7 Andrew Dove Supersaturation in the Boolean Lattice
  Turán's theorem begs the question: given fixed integers $n$ and $m$ and a fixed graph $H$, over all graphs with $n$ vertices and $m$ edges, which has the minimum number of subgraphs isomorphic to $H$? There is an analogous question for the Boolean lattice: given fixed integers $n$ and $m$ and fixed poset $P$, for all families $F$ contained in $B(n)$ where $|F|=m$, which family has the minimum number of subposets of $F$ isomorphic to $P$? In 1966, Kleitman answered this question for $P$ being a single edge. I will be outlining this proof as well as discussing possible further advances in answering this question.
• Oct 31 Andrew Dove Hamiltonian Cycles and Symmetric Chains in Boolean Lattices
  This is a paper by Noah Streib and William T. Trotter. Let $B(n)$ be the subset lattice of $\{1,2,\dots,n\}$. Sperner's theorem states that the width of $B(n)$ is equal to the size of its biggest level. There have been several elegant proofs of this result, including an approach that shows that $B(n)$ has a symmetric chain partition. Another famous result concerning $B(n)$ is that its cover graph is Hamiltonian. Motivated by these ideas and by the Middle Two Levels conjecture, they consider posets that have the Hamiltonian Cycle-Symmetric Chain Partition (HC-SCP) property. A poset of width $w$ has this property if its cover graph has a Hamiltonian cycle which parses into $w$ symmetric chains. They show that the subset lattices have the HC-SCP property. I will demonstrate this proof and look more at open questions in the area.
• Oct 24 É. Czabarka The Convex Hull Method II.
  Last time we described the idea of and the results obtained by the Convex Hull method. We will continue with the proof technique that allows to show that the extreme points of the convex hull of certain kind of set families are the profiles of the homogeneous families.
• Oct 17 É. Czabarka The Convex Hull Method I.
  The entries of the profile matrix of a set family give the number of elements of a given size in the set family. This concept can be extended to $M$-part set families giving rise to $M$ dimensional arrays. These arrays then can be viewed as vectors in an appropriate higher dimensional space. The vertices of the convex hull of profile matrices of certain families of sets were described by P.L. Erdős, P. Frankl, and G.O.H. Katona in 1985, facilitating the optimization of linear functions of the entries of profile matrices of members of the family in question. In 1986 P.L. Erdős and G.O.H. Katona adapted the method for $M$-part Sperner families. In the upcoming lectures I will introduce the method, sketch the proof and show our recent extensions to $M$-part $k$-dimensional Sperner multi-families satisfying certain extra conditions. Our results have new consequences even to $M$-part Sperner families that were not covered by the Erdős-Katona result. Joint work with H. K. Aydinian and L.A. Székely
• Oct 10 László A. Székely, Threshold functions for distinct parts: revisiting Erdős-Lehner
  We study four problems: put $n$ distinguishable/non-distinguishable balls into $k$ non-empty distinguishable/non-distinguishable boxes randomly. What is the threshold function $k=k(n) $ to make almost sure that no two boxes contain the same number of balls? The non-distinguishable ball problems are essentially equivalent to the Erdős-Lehner asymptotic formula for the number of partitions of the integer $n$ into $k$ parts with $k=o(n^{1/3})$. The problem is motivated by the statistics of an experiment, where we only can tell whether outcomes are identical or different. This is joint work with É. Czabarka and M. Marsili.
• October 4. 1:00pm-2:00 pm LC 312 G.O.H. Katona, Towards a structured Baranyai Theorem
  Baranyai's theorem states that if $k$ divides $n$ then there are $\binom{n-1}{k-1}$ partitions of the $n$-element set into $k$-element subsets in such a way that every $k$-element subset occurs in exactly one of these partitions. However nothing is known about the pairwise relation of the partitions. We will show some results moving in this direction. The objects considered here will be families of $\ell$ pairwise disjoint $k$-element sets rather than partitions (one can call them partial partitions). We say that two partial partitions are far if there are no two pairs of classes in these partitions with pairwise intersection more than $k/2$. It is proved that if $n$ is large, one can find such partial partitions far from each other in such a way that every $k$-element subset, with a few (bounded number) exceptions, is in one of them exactly once.
• Sept. 26 Aaron Dutle, Graph Odometry
  A delivery company sets up shop on a vertex $v$ of an edge-weighted graph $G$. Unluckily, the company truck is too large to make a U-turn (except at the company lot), so every trip made must be a non-backtracking closed walk from $v.$ After making each delivery, the driver records the distance traveled, i.e., the sum of the weights of the edges traveled, counted with multiplicity. What conditions must our graph satisfy so that the weight of every edge can be determined? How many walks are needed? Does the location of the start vertex matter? We address these and other questions.
• Sept. 19 Linyuan "Lincoln" Lu, Turán Problems on Non-uniform Hypergraphs
  Motivated by extremal poset problems, we will study the Turán problems on non-uniform hypergraphs. A (non-uniform) hypergraph $H$ is a pair $(V,E)$ with the vertex set $V$ and the edge set $E\subseteq 2^{V}$. Here we have no restriction on the cardinalities of edges. The set $R(H):=\{|F|\colon F\in E\}$ is called the set of its edge types. For a non-uniform hypergraph $G$ on $n$ vertices, we define the Lubell function of $G$ as $h(G)=\sum\limits_{F\in E(G)}\frac{1}{\binom{n}{|F|}}.$ For a given hypergraph $H$, we study the extremal hypergraphs with maximum Lubell values $h(G)$ among all $H$-free hypergraphs $G$ of the same edge types of $H$. (This a preliminary report, joint work with Travis Johnston.)
• Sept. 12 Linyuan "Lincoln" Lu, On crown-free families of subsets
  The crown $O_{2t}$ is a height-2 poset whose Hasse diagram is a cycle of length $2t$. A family $F$ of subsets of $[n]:=\{1,2,\ldots, n \}$ is $O_{2t}$-free if $O_{2t}$ is not a weak subposet of $(F,\subseteq)$. Let $La(n,O_{2t})$ be the largest size of $O_{2t}$-free families of subsets of $[n]$. De Bonis-Katona-Swanepoel proved $La(n,O_{4})= {n\choose \lfloor \frac{n}{2} \rfloor} + {n\choose \lceil \frac{n}{2} \rceil}$. Griggs and Lu proved that $La(n,O_{2t})=(1+o(1)) {n\choose \lfloor \frac{n}{2} \rfloor}$ for all even $t\ge 4$. In this talk, we will prove $La(n,O_{2t})=(1+o(1)) {n\choose \lfloor \frac{n}{2} \rfloor}$ for all odd $t\geq 7$.

Seminars in past semesters:

• Combinatorics Seminar in Spring, 2009.
• Combinatorics Seminar in Fall, 2008.
• Combinatorics Seminar in Spring, 2008.
• Combinatorics Seminar in Fall, 2007.
• Combinatorics Seminar in Spring, 2007.
• Combinatorics Seminar in Fall, 2006.
• Combinatorics Seminar in Spring, 2006.
• Combinatorics Seminar in Fall, 2005.