Seminar Calendar
for Graph Theory and Combinatorics events the next 12 months of Sunday, January 1, 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.
    December 2016           January 2017          February 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    1  2  3  4  5  6  7             1  2  3  4
  4  5  6  7  8  9 10    8  9 10 11 12 13 14    5  6  7  8  9 10 11
 11 12 13 14 15 16 17   15 16 17 18 19 20 21   12 13 14 15 16 17 18
 18 19 20 21 22 23 24   22 23 24 25 26 27 28   19 20 21 22 23 24 25
 25 26 27 28 29 30 31   29 30 31               26 27 28            
                                                                   

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.