ISU Discrete Math Seminar

Froggies on a pond

They get scared and hop along

Scaring others too.

Their erratic gate

Gives us tools to calculate

LCS of words.

A sign pattern is a matrix with entries coming from the set \(\{0,1,-1\}\). The entries of a sign pattern are used to encode the signs of the entries in real matrices. A long-standing open problem is to classify the sign patterns that allow orthogonality, i.e. classify sign patterns that have an orthogonal realization. We investigate various necessary conditions for a sign pattern to allow orthogonality. We also utilize the theory of smooth manifolds to develop a technique for constructing sign patterns of orthogonal matrices.

A longstanding open problem asks to give the maximum number \(N(d)\) of equiangular lines through the origin in \(C^d\) or \(R^d\). In the complex case, it is known that \(N(d) \leq d^2\), and it is widely believed this is attained for EVERY \(d > 1\). In the real case, it is known that \(N(d) \leq d(d+1)/2\), and it is widely believed this is attained for NO \(d > 23\). These are hard problems, and we will not solve them in this talk. What we will do is discuss equiangular lines in classical geometries over finite fields, and show that the analogous bounds are attained infinitely often. We will also discuss interactions with the real and complex problems, and explain how almost every known strongly regular graph arises from equiangular lines over a finite field.

Joint with Gary Greaves, John Jasper, and Dustin Mixon.

A set \(K\) in the \(n\)-dimensional vector space \(F_q^n\) over finite field \(F_q\) is called a Kakeya set if it contains a line in every direction. Dvir proved that the size \(|K|\) is at least \(c_nq^n\), where \(c_n=1/n!\) by using polynomial method. Recently, We improved the bound to \(c_n=1/2^{n-1}\), which is the best possible constant.

In this entry point into the subject, combining two elementary proofs, we decrease the gap between the upper and lower bounds by \(0.2\%\) in a classical combinatorial number theory problem. We show that the maximum size of a Sidon set of \(\{ 1, 2, \ldots, n\}\) is at most \(\sqrt{n}+ 0.998n^{1/4}\) for sufficiently large \(n\).

The talk is based on joint work with Zoltan Furedi and Souktik Roy.

In 1954, Kővári–Sós–Turán gave an upper bound on the number of edges in an \(n\)-vertex \(K_{s,t}\)-free. We show that the bound is asymptotically tight for \(t>C^s\), improving on the works of Alon, Kollár, Rónyai, Szabó.

In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph \(H\) is the infimum over all \(d\) for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least \(d\) contains \(H\). In particular, they raise the questions of determining the uniform Turán densities of \(K_4^{(3)-}\) and \(K_4^{(3)}\). The former question was solved only recently in [Israel J. Math. 211 (2016), 349–366] and [J. Eur. Math. Soc. 97 (2018), 77–97], while the latter still remains open for almost 40 years. In addition to \(K_4^{(3)-}\), the only \(3\)-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97] and a specific family with uniform Turán density equal to \(1/27\).

In this talk, we give an introduction to the concept of uniform Turán densities, present a way to obtain lower bounds using color schemes, and give a glimpse of the proof for determining the uniform Turán density of the tight \(3\)-uniform cycle \(C_\ell^{(3)}\), \(\ell\ge 5\).

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph \(K_n\). For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When \(G\) is the \(4\)-cycle (or the \(4\)-cycle with a chord), we show that the set of plane drawings of \(G\) is geometric-packable, while this is not true when \(G\) is all but at most 3 other planar Hamiltonian graphs. A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph \(G\), we determine whether or not plane \(G\) is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of \(K_n\).

An ordered graph is a simple graph with an ordering on its vertices. We are interested in the ordered path \(P_n\), which is the monotone increasing path with \(n\) edges. The ordered size Ramsey number of \(P_r\) versus \(P_s\) is the minimum number of edges needed in an ordered graph \(H\) such that every red-blue coloring of the edges of \(H\) contains a red copy of \(P_r\) or a blue copy of \(P_s\). In this talk, we will present upper and lower bounds on this Ramsey number which are tight up to a polylogarithmic factor and discuss connections to other Ramsey problems for paths. This is joint work with József Balogh, Felix Clemen, and Mikhail Lavrov.

The number of homomorphisms from a graph \(H\) to a graph \(G\), denoted by \(\textup{hom}(H;G)\), is the number of maps from \(V(H)\) to \(V(G)\) that yield a graph homomorphism, i.e., that map every edge of \(H\) to an edge of \(G\). Given a fixed collection of finite simple graphs \(\{H_1, \ldots, H_s\}\), the graph profile is the set of all vectors \((\textup{hom}(H_1; G), \ldots , \textup{hom}(H_s; G))\) as \(G\) varies over all graphs. Graph profiles essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and relate the results to some questions in extremal graph theory.

In this talk, we will survey the relevant literature, namely degree and edge conditions for Hamiltonicity and long cycles in graphs, including bipartite and \(k\)-partite results. We will then prove that if \(G\) is a balanced tripartite graph on \(3n\) vertices, \(G\) must contain a cycle of length at least \(3n-1\), provided that \(e(G) \geq 3n^2-4n+5\) and \(n\geq 14\). The result will be generalized to long cycles for 2-connected graphs when the minimum degree is large enough. Joint work with G. Araujo-Pardo, J. Faudree, K. Hogenson, R. Kirsch, L. Lesniak, and J. McDonald.

Ehrhart theory is a topic in geometric combinatorics which involves the enumeration of lattice points in integral dilates of polytopes. We introduce panhandle matroids, which generalize the previously studied uniform matroids and minimal connected matroids. We provide a formula for the Ehrhart polynomial of the matroid polytope of panhandle and paving matroids. We also make substantial progress toward proving that the coefficients of the Ehrhart polynomials for panhandle matroids are positive, and we reduce this problem to a purely combinatorial enumeration problem.

For any positive integer \(t\), a \(t\)-broom is a graph obtained from \(K_{1,t+1}\) by subdividing an edge once. We show that, for graphs \(G\) without induced \(t\)-brooms, \(\chi(G) = o(\omega(G)^{t+1})\), where \(\chi(G)\) and \(\omega(G)\) are the chromatic number and clique number of \(G\), respectively. When \(t=2\), this answers a question of Schiermeyer and Randerath. Moreover, for \(t=2\), we strengthen the bound on \(\chi(G)\) to \(7.5\omega(G)^2\), confirming a conjecture of Sivaraman. For \(t\geq 3\) and {\(t\)-broom, \(K_{t,t}\)}-free graphs, we improve the bound to \(o(\omega^{t-1+\frac{2}{t+1}})\). Joint work with Joshua Schroeder, Zhiyu Wang, and Xingxing Yu.

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.