Department of

# Mathematics

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

.
events for the
events containing

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

3:00 pm in 241 Altgeld Hall,Tuesday, January 24, 2017

#### 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

3:00 pm in 241 Altgeld Hall,Tuesday, January 31, 2017

#### DP-colorings of graphs with high chromatic number

###### Anton Bernshteyn (Illinois Math)

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

3:00 pm in 241 Altgeld Hall,Tuesday, February 7, 2017

#### The maximum number of cliques in graphs without long cycles

###### Ruth Luo (Illinois Math)

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

3:00 pm in 241 Altgeld Hall,Tuesday, February 14, 2017

#### Families in posets minimizing the number of comparable pairs

###### Sarka Petrickova (Illinois Math)

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

3:00 pm in 241 Altgeld Hall,Tuesday, February 21, 2017

#### Reconstruction from the deck of $k$-vertex induced subgraphs

###### Douglas B. West (Illinois Math and Zhejiang Normal University)

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

3:00 pm in 241 Altgeld Hall,Tuesday, February 28, 2017

#### Distance-uniform graphs with large diameter

###### Misha Lavrov (Carnegie Mellon University)

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

3:00 pm in 241 Altgeld Hall,Tuesday, March 7, 2017

#### The strong chromatic index of graphs with maximum degree four is at most 21

###### Gexin Yu (College of William & Mary)

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

3:00 pm in 241 Altgeld Hall,Tuesday, March 14, 2017

#### Rooted forests that avoid sets of permutations

###### Katherine Anders (The University of Texas at Tyler)

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

3:00 pm in 241 Altgeld Hall,Tuesday, April 11, 2017

#### On the number of Hamiltonian subsets

###### Jaehoon Kim (University of Birmingham)

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

3:00 pm in 241 Altgeld Hall,Tuesday, April 18, 2017

#### Permutations fixing k-sets and applications to group theory

###### Kevin Ford (Illinois Math)

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

3:00 pm in Altgeld Hall,Tuesday, April 25, 2017

#### Small $k$-certificate in hypergraphs and representing all min-cuts

###### Chao Xu (Illinois Computer Science)

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

3:00 pm in 241 Altgeld Hall,Tuesday, August 29, 2017

#### On-line size Ramsey number for ordered tight paths

###### Douglas West (Illinois Math and Zhejiang Normal University)

Abstract: An ordered hypergraph is a hypergraph $H$ with a specified linear ordering of the vertices. The appearance of an ordered hypergraph $G$ in $H$ must respect the specified order on $V(G)$. In on-line Ramsey theory, Builder iteratively presents edges that Painter must immediately color. The $t$-color on-line size Ramsey number $R'_t(G)$ of an ordered hypergraph $G$ is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using $t$ colors to produce a monochromatic copy of $G$. The monotone tight path $P(r,k)$ is the ordered hypergraph with $r$ vertices whose edges are all sets of $k$ consecutive vertices. We obtain good bounds on $R'_t(P(r,k))$. Letting $m=r-k+1$ (the number of edges in $P(r,k)$), we prove $m^{t-1}/(3\sqrt t) \le R'(P(r,2)) \le tm^{t+1}$. For general $k$, a trivial upper bound is $\left({N \atop k}\right)$, where $N$ is the vertex Ramsey number of $P(r,k)$ and is a tower of height $k-2$. We prove $N/(k\log N) \le R'_t(P(r,k)) \le N(\log N)^{2+c}$, where $c$ is any positive constant and $t(m-1)$ is sufficiently large. Our upper bounds improve prior results when $t$ grows faster than $m/\log m$, and our methods yield another derivation of the vertex Ramsey number. We also generalize our results to $l$-loose monotone paths, where each successive edge begins $l$ vertices after the previous edge (the tight path is 1-loose). This work is joint with Xavier Pérez Giménez and Pawel Pralat.

Tuesday, September 5, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, September 5, 2017

#### An improved upper bound for the Hales-Jewett number HJ(4,2)

###### Mikhail Lavrov (Illinois Math)

Abstract: In the $n$-dimensional grid $[t]^n = \{1, 2, \dots, t\}^n$, a combinatorial line is an injective function $\ell : [t] \to [t]^n$ such that for each coordinate $1 \le i \le n$, $\ell_i$ is either constant or the identity function on $[t]$. An example of such a line in $[4]^5$ is the function $\ell(x) = (3, x, 1, x, 4)$ whose image is the set of four points (3,1,1,1,4), (3,2,1,2,4), (3, 3,1,3,4), (3,4,1,4,4). A classic result in Ramsey theory, the Hales-Jewett theorem, asserts that for all values of the parameters $t$ and $r$, there is a sufficiently large $n = HJ(t,r)$ such that any $r$-coloring of $[t]^n$ will contain a combinatorial line whose points are monochromatic. Apart from $HJ(2,r)$ for variable $r$ and $HJ(3,2)$ which have all been determined exactly, good bounds on values of $HJ(t,r)$ are generally not known. Even for the small case $HJ(4,2)$, the best result known is a general result due to Shelah, which gives an upper bound between $2 \uparrow \uparrow 7$ and $2 \uparrow \uparrow 8$: quite far from the best known lower bound of 12. We show that the upper bound can be improved to $10^{11}$.

Tuesday, September 19, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, September 19, 2017

#### Ramsey numbers of 2-interval chromatic ordered graphs

###### Dana Neidinger (Illinois Math)

Abstract: An ordered $G$ is a graph together with a specified linear ordering on the vertices, and its interval chromatic number is the minimum number of independent sets consisting of consecutive vertices that are needed to partition the vertex set. The $t$-color Ramsey number $R_t(G)$ of an ordered graph $G$ is the minimum number of vertices of an ordered complete graph such that every edge-coloring by $t$ colors contains a copy of $G$ in some color $i$, where the copy of $G$ preserves the original ordering on $G$. We obtain lower bounds linear in the number of vertices for the ordered Ramsey numbers of certain classes of 2-ichromatic ordered graphs using the methodology of Balko, Cibulka, Král, and Kynčl. We also determine the exact value of the $t$-color Ramsey number for two families of 2-ichromatic ordered graphs. We prove a linear upper bound for a class of 2-ichromatic ordered graphs.

Tuesday, September 26, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, September 26, 2017

#### An improved lower bound for Folkman's theorem

###### József Balogh (Illinois Math)

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.

Tuesday, October 3, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, October 3, 2017

#### Baire measurable colorings of group actions

###### Anton Bernshteyn (Illinois Math)

Abstract: A typical combinatorial problem is that of coloring, i.e., assigning a "color" to each element of a given structure in a way that fulfills a specified set of constraints. For instance, one might want to color the vertices of a graph so that adjacent vertices receive different colors. Standard compactness arguments usually reduce the general situation to the case when the underlying structure is finite. However, as compactness is inherently dependent upon the Axiom of Choice, this approach is "non-constructive" and the colorings obtained in this way can be quite "pathological," for example, non-measurable. Nonetheless, maybe not all is lost: It is conceivable that the existence of a "well-behaved" coloring is equivalent to a stronger assertion in the finite case, perhaps that a finite coloring can be found via an algorithm of a certain form. In this talk I will describe a result that confirms this suspicion when the underlying notion of "well-behavedness" is Baire measurability and the structure that we wish to color is induced by the shift action of a countable group.

Tuesday, October 10, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, October 10, 2017

#### Packing chromatic number of cubic graphs

###### Xujun Liu (Illinois Math)

Abstract: A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,\dots, V_k$ such that for each $1\leq i\leq k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\geq 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$. Joint work with József Balogh and Alexandr Kostochka.

Tuesday, October 17, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, October 17, 2017

#### List Coloring Cartesian Products of Graphs: Criticality and the List Color Function

###### Hemanshu Kaul (Illinois Institute of Technology)

Abstract: The list chromatic number of the Cartesian product of graphs is not well understood. The best result is by Borowiecki, Jendrol, Kral, & Miskuf (2006) who proved that the list chromatic number of the Cartesian product of two graphs can be bounded in terms of the list chromatic number and the coloring number of the factors, implying a bound exponential in the list chromatic number of the factors. We show how the knowledge of the list color function (list coloring analogue of the chromatic polynomial) can be applied to list coloring of Cartesian products whose one factor is a strong k-chromatic choosable graph. We introduce the notion of strongly chromatic choosable graphs, that includes odd cycles, cliques, many more infinite families of graphs, and the join of a clique with any other such graph, as a strict generalization of the notion of strong critical graphs (Stiebitz, Tuza & Voigt, 2008). This leads to improved bounds on choosability of Cartesian product of certain large classes of graphs and to classes of chromatic-choosable Cartesian products of graphs. This is joint work with Jeffrey Mudrock.

Tuesday, October 24, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, October 24, 2017