ISU Discrete Math Seminar

In the talk, we will discuss edge-colorings of (sub)cubic graphs. Namely, we will consider edge-colorings in which we work with two types of colors: the proper and the strong colors. The edges colored with the same proper color form a matching (no two edges are incident), and the edges colored with the same strong color form an induced matching (no two edges are incident to a common edge). Clearly, when all the colors are proper, the edge-coloring of a graph is proper, and if all the colors are required to be strong, we have a strong edge-coloring. The tight upper bounds for the chromatic indices of the above two extremal colorings are long established, thus we will focus to edge-colorings with combinations of proper and strong colors. Such colorings have been investigated before, but only as a tool to obtain results for other types of colorings. Systematically, they have been introduced just recently by Gastineau and Togni as an edge-coloring variation of \(S\)-packing colorings. We will present results on the topic and give a number of open problems. Joint work with Herve Hocquard and Dimitri Lajou.

A conjecture of Erdős from 1967 asserts that any graph on n vertices which does not contain a fixed \(r\)-degenerate bipartite graph \(F\) has at most \(Cn^{2−1/r}\) edges, where \(C\) is a constant depending only on \(F\). We show that this bound holds for a large family of \(r\)-degenerate bipartite graphs, including all \(r\)-degenerate blow-ups of trees. Our results generalize many previously proven cases of the Erdős conjecture, including the related results of Füredi and Alon, Krivelevich and Sudakov. Joint work with Oliver Janzér and Zoltán Lóránt Nagy.

Let \({\rm ex}_{\mathcal{P}}(n,T,H)\) denote the maximum number of copies of \(T\) in an \(n\)-vertex planar graph which does not contain \(H\) as a subgraph. When \(T=K_2\), \({\rm ex}_{\mathcal{P}}(n,T,H)\) is the well studied function, the planar Turán number of \(H\), denoted by \({\rm ex}_{\mathcal{P}}(n,H)\). The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both \({\rm ex}_{\mathcal{P}}(n,C_4)\) and \({\rm ex}_{\mathcal{P}}(n,C_5)\). Later on, Y. Lan, et al. (2019) continued this topic and proved that \({\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}\). In this talk, we give a sharp upper bound \({\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7\), for all \(n\geq 18\), which improves Lan’s result.

What is the maximum number of copies of a graph \(H\) that can appear in an \(n\)-vertex planar graph? In this talk, we introduce a general technique which can be used to bound this quantity in terms of an optimization problem over weighted graphs. By using this technique, we attain asymptotically tight bounds on the maximum number of \(P_7\)’s, \(C_6\)’s and \(C_8\)’s in a planar graph. Additionally, we demonstrate the strength of this technique by re-deriving the known asymptotics of the maximum number of \(P_5\)’s and \(C_4\)’s, showing that these two cases are essentially trivial. This technique can theoretically be used to prove asymptotically tight bounds on the maximum number of odd paths and even cycles in a planar graph in general, but we’ll leave that endeavor to future researchers (maybe even you)! (Joint work with Ryan Martin)

Given a finite set \(P \subseteq \mathbb{R}^d\), points \(a_1,a_2,\dotsc,a_{\ell} \in P\) form an \(\ell\)-hole in \(P\) if they are the vertices of a convex polytope which contains no points of \(P\) in its interior. We construct arbitrarily large point sets in general position in \(\mathbb{R}^d\) having no holes of size \(2^{7d}\) or more. This improves the previously known upper bound of order \(d^{d+o(d)}\) due to Valtr. Our construction uses a certain type of designs, originating from numerical analysis, known as ordered orthogonal arrays. The bound may be further improved, to roughly \(4^d\), via an approximate version of such designs. Joint work with Boris Bukh and Ting-Wei Chao.

Where extremal combinatorialists wish to optimise a discrete parameter over a family of large objects, probabilistic combinatorialists study the statistical behaviour of a randomly chosen object in such a family. In the context of representable matroids (i.e. the columns of a matrix) over \(F_2\), one well-studied distribution is to fix a small \(k\) and large \(m\) and randomly generate \(m\) columns with \(k\) \(1\)’s. Indeed, when \(k=2\), this is the graphic matroid of the Erdos-Renyi random graph \(G_{n,m}\).

We turn back to the simplest corresponding extremal question in this setting. What is the maximum number of weight-\(k\) columns a matrix of rank \(\leq n\) can have? We show that, once \(n\geq N_k\), one cannot do much better than taking only \(n\) rows and all available weight-\(k\) columns. This partially confirms a conjecture of Ahlswede, Aydinian and Khachatrian, who believe one can take \(N_k=2k\).

This is joint work with Wesley Pegden.

A polytope \(P\) is the convex hull of finitely many points in Euclidean space. For polytopes \(P\) and \(Q\), we say that \(Q\) is a Minkowski summand of \(P\) if there exists some polytope \(R\) such that \(Q+R=P\). The type cone of \(P\) encodes all of the (weak) Minkowski summands of P. In general, combinatorially isomorphic polytopes can have different type cones. We will first consider type cones of polygons, and then show that if \(P\) is combinatorially isomorphic to a product of simplices, then the type cone is simplicial. No previous knowledge of polytopes will be assumed. This is joint work with Federico Castillo, Joseph Doolittle, Michael Ross, and Li Ying.

A Kempe swap in a properly colored graph recolors one component of the subgraph induced by two colors, interchanging them on that component. Two \(k\)-colorings are Kempe \(k\)-equivalent if we can transform one into the other by a sequence of Kempe swaps, such that each intermediate coloring uses at most \(k\) colors. Meyniel proved that if \(G\) is planar, then all 5-colorings of \(G\) are Kempe 5-equivalent; this proof relies heavily on the fact that planar graphs are 5-degenerate. To prove an analogous result for toroidal graphs would require handling 6-regular graphs. That is the focus of this paper. We show that if \(G\) is a 6-regular graph with an embedding in the torus where every non-contractible cycle has length at least 7, then all 5-colorings of \(G\) are Kempe 5-equivalent. Bonamy, Bousquet, Feghali, and Johnson asked specifically about the case that \(G\) is a triangulated toroidal grid, which is formed from the Cartesian product of \(C_m\) and \(C_n\) by adding a diagonal inside each 4-face, with all diagonals parallel. By slightly modifying the proof of our main result, we answer their question affirmatively when \(m\geq 6\) and \(n\geq 6\). This is joint work with Reem Mahmoud.

We wish to locate an intruder who is hiding at one of the vertices of a graph \(G\). At each step, we are allowed to ‘check’ an arbitrary set of \(k\) vertices. If the intruder is presently at any of those vertices, then we win. Otherwise, the intruder may choose to move to an adjacent vertex or remain in place. The intruder is ‘invisible’: we have no way of knowing if or where the intruder moves. We call the smallest \(k\) such that we can guarantee the capture of the intruder after finitely many steps the search number of \(G\). In this talk I will describe some results and problems around the search number, with a particular emphasis on its behavior under edge-subdivisions. This is joint work with Eugene Lee (Carnegie Mellon University).

The Mycielskian of a graph \(G\), \(\mu(G)\), is constructed by adding a shadow vertex \(u_i\) for each vertex \(v_i\) in \(G\), one additional vertex \(w\), and edges so that \(N(u_i) = N(v_i)\cup \{w\}\). The distinguishing number of a graph \(G\) is the fewest number of colors needed so that the only color-preserving automorphism is trivial. In 2019, Alikhani and Soltani showed that the distinguishing number of \(\mu(G)\) is at most one more than the distinguishing number of \(G\) when \(G\) is twin-free and conjecture that the distinguishing number of \(\mu(G)\) is at most the distinguishing number of \(G\) for most graphs. We prove a stronger version of their conjecture, as well as results for generalized Mycielskians, and determining numbers. This is joint work with Debra Boutin, Sally Cockburn, Sarah Loeb, Kat Perry, and Puck Rombach.

How to place n points inside the d-dimensional unit cube so every large axis-parallel box contains at least one point? We discuss the motivation as well as a partial solution to this problem. This is a joint work with Ting-Wei Chao.

Adversarial networks model scenarios in which a malicious outside actor can corrupt legitimate messages being sent between users in a communication network. The one-shot capacity gives a measure of how many symbols can be sent across the network reliably in a single transmission round. In this talk, we discuss the tightness of a previous upper bound on the one-shot capacity of adversarial networks that was derived by reducing the problem to a cut-set of the underlying directed graph. We show that in a minimal example called the Diamond Network, this cut-set bound is not tight. In fact, the one-shot capacity is no longer even an integer. We then give a sufficient condition for tightness of the bound in a particular class of networks. To conclude, we exhibit an interesting example that both demonstrates that the aforementioned condition is not necessary and gives insight into how we might leverage the idea of message authentication to achieve capacity over adversarial networks in general.

In this talk we will discuss what subgraphs can be guaranteed if a graph has a large eigenvalue. This is the spectral analog of the Turán problem and was first raised by Brualdi and Solheid and Nikiforov. We will give an overview of how to prove theorems in this area and will discuss some intuition for how to guess what the extremal graph(s) should be. This is joint work with Sebi Cioaba, Dheer Desai, Lihua Feng, Josh Tobin, and Xiao-Dong Zhang.

A family of subsets of \([n]\) is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics, starting with the well-known Erdos-Ko-Rado Theorem. We consider two extensions of it:

Counting variant: Frankl–Kupavskii and Balogh–Das–Liu–Sharifzadeh–Tran showed that for \(n\geq 2k + c\sqrt{k\ln k}\), almost all \(k\)-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for \(n\geq 2k+ 100\ln k\).

Random variant: For positive integers \(n\) and \(k\) with \(n\geq 2k+1\), the Kneser graph \(K(n,k)\) is the graph with vertex set consisting of all \(k\)-sets of \(\{1,\dots,n\}\), where two \(k\)-sets are adjacent exactly when they are disjoint. Let \(K_p(n,k)\) be a random spanning subgraph of \(K(n,k)\) where each edge is included independently with probability \(p\). Bollobás, Narayanan, and Raigorodskii asked for what \(p\) does \(K_p(n,k)\) have the same independence number as \(K(n,k)\) with high probability. Building on work of Das and Tran and of Devlin and Kahn, we resolve this question.

Our proofs uses, among others, the graph container method and the Das–Tran removal lemma.

It is joint work with Lina Li, Ramon Garcia, Adam Wagner; and with Robert Krueger and Haoran Luo.