Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Friday, April 21, 2017.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      March 2017             April 2017              May 2017      
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
           1  2  3  4                      1       1  2  3  4  5  6
  5  6  7  8  9 10 11    2  3  4  5  6  7  8    7  8  9 10 11 12 13
 12 13 14 15 16 17 18    9 10 11 12 13 14 15   14 15 16 17 18 19 20
 19 20 21 22 23 24 25   16 17 18 19 20 21 22   21 22 23 24 25 26 27
 26 27 28 29 30 31      23 24 25 26 27 28 29   28 29 30 31         
                        30                                         

Tuesday, January 24, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 24, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Many $T$ copies in $H$-free subgraphs of random graphs
Abstract: For two fixed graphs $T$ and $H$ let $ex(G(n,p),T,H)$ be the random variable counting the maximum number of copies of $T$ in an $H$-free subgraph of the random graph $G(n,p)$. We show that for the case $T=K_m$ and $\chi(H)>m$ the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and $m_2(H)=\max_{H'\subset H, |V(H')|\geq 3}\left\{ \frac{e(H')-1}{v(H')-2} \right\}$. When $m_2(H)>m_2(K_m)$ we prove that with high probability, depending on the value of $p$, either one can keep almost all copies of $K_m$ in an $H$-free subgraph of $G(n,p)$, or it is asymptotically best to take a $\chi(H)-1$ partite subgraph of $G(n,p)$. The transition between these two behaviors occurs at $p=n^{-1/m_2(H)}$. When $m_2(H)< m_2(K_m)$, the above cases still exist, however for $\delta>0$ small at $p=n^{-1/m_2(H)+\delta}$ one can typically still keep most of the copies of $K_m$. The reason for this is that although $K_m$ has the minimum average degree among the $m$-color-critical graphs, it does not have the smallest $m_2(G)$ among such graphs. This is joint work with N. Alon and C. Shikhelman.

Tuesday, January 31, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 31, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Anton Bernshteyn (Illinois Math)
DP-colorings of graphs with high chromatic number
Abstract: Let $G$ be an $n$-vertex graph with chromatic number $\chi(G)$. Ohba's conjecture (now a celebrated theorem due to Noel, Reed, and Wu) claims that whenever $\chi(G) \geq (n-1)/2$, the list chromatic number of $G$ equals $\chi(G)$. DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle. We establish an analog of Ohba's conjecture for the DP-chromatic number; namely we show that the DP-chromatic number of $G$ also equals $\chi(G)$ as long as $\chi(G)$ is ``sufficiently large''. In contrast to the list coloring case, ``large'' here means $\chi(G)\geq n-O(\sqrt{n})$, and we also show that this lower bound is best possible (up to the constant factor in front of $\sqrt{n}$). This is joint work with Alexandr Kostochka and Xuding Zhu.

Tuesday, February 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 7, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Ruth Luo (Illinois Math)
The maximum number of cliques in graphs without long cycles
Abstract: The Erdős-Gallai Theorem states that for $k\geq 3$ every graph on $n$ vertices with more than $\frac{1}{2}(k-1)(n-1)$ edges contains a cycle of length at least $k$. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples $H_{n,k,t}$ and $H_{n,k,2}$. In this talk, we generalize the result of Kopylov to bound the number of $s$-cliques in a graph with circumference less than $k$. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of $s$-cliques in a graph with no path on $k$-vertices.

Tuesday, February 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 14, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Sarka Petrickova (Illinois Math)
Families in posets minimizing the number of comparable pairs
Abstract: Given a poset $P$, we say a family $\mathcal{F} \subseteq P$ is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the centeredness property if for any $M$, amongst all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ (where $(A_1,\dots,A_n)\le (B_1,\dots,B_n)$ if $A_i\le B_i$ for each $i\in [n]$) also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbf{F}_q^n$ has the centeredness property. This is joint work with Jozsef Balogh and Adam Zsolt Wagner.

Tuesday, February 21, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 21, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Douglas B. West (Illinois Math and Zhejiang Normal University)
Reconstruction from the deck of $k$-vertex induced subgraphs
Abstract: The $k$-deck of a graph is its multiset of subgraphs induced by $k$ vertices; we ask whether the $k$-deck determines the graph. We show that a complete $r$-partite graph is determined by its $(r+1)$-deck. Letting $n=|V(G)|$, we generalize a result of Bollobás by showing that for $l=(1-o(1))n/2$, almost every graph $G$ is determined by various sets of ${l+2\choose 2}$ subgraphs with $n-l$ vertices. However, when $l=n/2$, the entire $(n-l)$-deck does not always determine whether $G$ is connected (it fails for $n$-vertex paths). We strengthen a result of Manvel by proving for each $l$ that when $n$ is sufficiently large (at least $l^{l^2}$), the $(n-l)$-deck determines whether $G$ is connected ($n\ge25$ suffices when $l=3$, and $n\le 2l$ cannot suffice). Finally, for every graph $G$ with maximum degree $2$, we determine the least $k$ such that $G$ is reconstructible from its $k$-deck, which involves extending a result of Stanley. This is joint work with Hannah Spinoza.

Tuesday, February 28, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 28, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Misha Lavrov (Carnegie Mellon University)
Distance-uniform graphs with large diameter
Abstract: We say that a graph is epsilon-distance-uniform if there is a value d (called the critical distance) such that, for every vertex v, all but an epsilon fraction of the other vertices are at distance exactly d from v. Random graphs are distance-uniform with logarithmic critical distance, and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that the critical distance (equivalently, the diameter) of a distance-uniform graph must always be logarithmic. In this talk, we use a generalization of the Towers of Hanoi puzzle to construct distance-uniform graphs with a much larger diameter: for constant epsilon, as large as n^O(1/log log n). We show that this construction is more or less worst possible for sufficiently small epsilon, leaving open the possibility that for large epsilon, much worse cases exist. This is joint work with Po-Shen Loh.

Tuesday, March 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 7, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Gexin Yu (College of William & Mary)
The strong chromatic index of graphs with maximum degree four is at most 21
Abstract: A strong edge-coloring of a graph $G$ is a coloring of the edges such that every color class induces a matching in $G$. The strong chromatic index of a graph is the minimum number of colors needed in a strong edge-coloring of the graph. In 1985, Erdős and Nešetřil conjectured that every graph with maximum degree $\Delta$ has a strong edge-coloring using at most $\frac{5}{4}\Delta^2$ colors if $\Delta$ is even, and at most $\frac{5}{4}\Delta^2 - \frac{1}{2}\Delta + \frac{1}{4}$ if $\Delta$ is odd. This conjecture is widely unresolved with the only verified case being for $\Delta = 3$, due independently to Andersen as well as Horák, Qing, and Trotter. In this paper, we show that the strong chromatic index of graphs (where we allow for multiple edges) with maximum degree at most four is always at most 21. This improves a previous bound due to Cranston and moves closer to the conjectured upper bound of 20. This is joint work with Mingfang Huang and Michael Santana.

Tuesday, March 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 14, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Katherine Anders (The University of Texas at Tyler)
Rooted forests that avoid sets of permutations
Abstract: An unordered rooted labeled forest avoids the pattern $\pi\in\mathcal{S}_n$ if the sequence obtained from the labels along the path from the root to any vertex does not contain a subsequence that is in the same relative order as $\pi$. We enumerate several classes of forests that avoid certain sets of permutations, including the set of unimodal forests, via bijections with set partitions with certain properties. This is joint work with Kassie Archer.

Tuesday, April 11, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 11, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Jaehoon Kim (University of Birmingham)
On the number of Hamiltonian subsets
Abstract: In 1981, Komlós conjectured that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify. This is joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.

Tuesday, April 18, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 18, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Kevin Ford (Illinois Math)
Permutations fixing k-sets and applications to group theory
Abstract: A $k$-set of a permutation $\pi\in S_n$ is a subset $I\in [n]$ of size $k$ which is itself permuted by $\pi$. Equivalently, $I$ is a product of a subset of the cycles of $\pi$. In this talk, we discuss two problems: (1) If one chooses $r>1$ permutations at random, what is the likelihood that for some large $k$ each contains a $k$-set? This has application to the problem of invariable generation of $S_n$, and is connected with a famous old problem of Erdős: to show that almost all integers have two divisors in some dyadic interval $(y,2y]$. (2) Given $k_1, k_2, \ldots, k_m$ what is the likelihood that a random $\pi$ has a $k_1$-set, $k_2$-set, ..., $k_m$-set (all disjoint)? Such bounds are applied to the problem of estimating how many permutations $\pi \in S_n$ lie in transitive subgroups of $S_n$ other than $S_n$ or $A_n$. This is joint work with Sean Eberhard, Ben Green and Dimitrios Koukoulopoulos.

Tuesday, April 25, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in Altgeld Hall,  Tuesday, April 25, 2017
 Del 
 Edit 
 Copy 
Submitted by molla.
Chao Xu (Illinois Computer Science)
Small $k$-certificate in hypergraphs and representing all min-cuts
Abstract: For a hypergraph $H=(V,E)$, a hypergraph $H'=(V,E')$ is called a $k$-certificate of $H$ if it preserves all the cut values up to $k$. That is, $|\delta_{H'}(S)| \geq \min(|\delta_H(S)|,k)$ for all $S\subset V$. Nagamochi and Ibaraki showed there exists a $k$-certificate with $O(kn)$ edges for graphs, where $n$ is the number of vertices. A similar argument shows this extends to hypergraphs. We show a stronger result of hypergraphs: there is a $k$-certificate with size (sum of degrees) $O(kn)$, and it can be obtained by removing vertices from edges in $H$. We also devise an algorithm that finds a representation of all min-cuts in a hypergraph in the same running time as finding a single min-cut. The algorithm uses Cunningham's decomposition framework, and different generalizations of maximum adjacency ordering. This is joint work with Chandra Chekuri.

Tuesday, August 29, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, August 29, 2017
 Del 
 Edit 
 Copy 
Submitted by mlavrov.
József Balogh (Department of Mathematics, University of Illinois)
An improved lower bound for Folkman's theorem
Abstract: Folkman's Theorem asserts that for each $k \in \mathbb N$, there exists a natural number $n=F(k)$ such that whenever the elements of $[n]$ are two-coloured, there exists a subset $A$ of $[n]$ of size $k$ with the property that all the sums of the form $\sum_{x\in B} x$, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same colour. In 1989, Erdős and Spencer showed that $F(k) \ge 2^{ck^2/\log k}$, where $c>0$ is an absolute constant; here, we improve this bound significantly by showing that $F(k) \ge 2^{2^{k-1}/k}$ for all $k \in \mathbb N$. Joint with Sean Eberhard, Bhargav Narayanan, Andrew Treglown, Adam Zsolt Wagner.