ISU Discrete Math Seminar

The originally-scheduled speaker had to postpone their talk, so I’ll step in and ramble on about some problem I think is interesting for an hour.

The notion of asymptotic dimension was introduced by Gromov to describe the large-scale dimensionality of metric spaces. We survey a number of recent results and open questions on this topic in the context of graph metrics.

Since we’re missing a speaker this week, I’ll ramble incoherently yet again about some problem I find interesting.

This paper is about moving between any two colorings of a graph via Kempe swaps. This problem has been studied intensively, and we generalize one of the major results from colorings to list-colorings. (This is joint work with Reem Mahmoud.)

In this talk, we fix a graph \(H\) and ask into how many vertices each vertex of a clique of size \(n\) can be “split” such that the resulting graph is \(H\)-free. Formally: A graph is an \((n,k)\)-graph if its vertex set is a pairwise disjoint union of \(n\) parts of size at most \(k\), such that there is an edge between any two distinct parts. Let \[f(n,H) = \min \{k \in \mathbb N : \text{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\}.\]

Barbanera and Ueckerdt observed that \(f(n, H)=2\) for any graph \(H\) that is not bipartite. If a graph \(H\) is bipartite and has a well-defined Turán exponent, i.e., \({\rm ex}(n, H) = \Theta(n^r)\) for some \(r\), we show that \(\Omega (n^{2/r-1}) = f(n, H) = O (n^{2/r -1} \log^{1/r} n)\). We extend this result to all bipartite graphs for which upper and a lower Turán exponents do not differ by much. In addition, we prove that \(f(n, K_{2,t}) =\Theta(n^{1/3})\) for any fixed integer \(t\geq 2\).

A celebrated conjecture of Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. We will discuss some results regarding this conjecture, as well as a generalization to hypergraphs posed by Aharoni and Zerbib.

We develop a method to study sufficient conditions for perfect mixed tilings. Our framework allows the embedding of bounded degree graphs \(H\) with components of sublinear order. As a corollary, we recover and extend the work of Kühn and Osthus regarding sufficient minimum degree conditions for perfect \(F\)-tilings (for an arbitrary fixed graph \(F\)) by replacing the \(F\)-tiling with the aforementioned graphs \(H\). Moreover, we obtain analogous results for degree sequences. Finally, we asymptotically resolve a conjecture of Komlós in a strong sense.

The paper was joint work with Felix Joos and Richard Lang, and can be found here https://arxiv.org/abs/2201.03944

This talk serves two purposes. First. it is an advertisement to the discrete community of an upcoming algebra & geometry seminar talk by Matt Mastroeni concerning some joint work on Chow rings of matroids. Second, it serves as an introduction to some exciting recent applications of algebraic geometry to the resolution of long-standing conjectures in combinatorics. The advances, spear-headed by June Huh, Botong Wang, and others, goes under the title ‘Hodge Theory for Combinatorial Geometries.’ The central player is the Chow ring of a matroid, a purely combinatorially defined ring attached to any matroid. I will try to give a gentle introduction to the area and discuss how Chow rings are used to resolve the Heron-Rota-Welsh conjecture and the Top Heavy Conjecture, which have their origins in graph theory and hyperplane arrangements, respectively.

We show that the minimum number of vertices of a simplicial complex with fundamental group \(\mathbb{Z}^{n}\) is at most \(O(n)\) and at least \(\Omega(n^{3/4})\). For the upper bound, we use a result on orthogonal 1-factorizations of \(K_{2n}\). For the lower bound, we use a fractional Sylvester-Gallai result. We will discuss these two results (orthogonal 1-factorizations, fractional Sylvester-Gallai) and give proof outlines for our asymptotic bounds. This is joint work with Florian Frick (Carnegie Mellon University).

Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. This notion formalizes a particularly simple way of "saving" colors while coloring a graph greedily. It turns out that many upper bounds on chromatic numbers follow from corresponding bounds on weak degeneracy. In this talk I will survey some of these bounds as well as state a number of open problems. This is joint work with Eugene Lee (Carnegie Mellon University).

There are many theorems about conditions under which various graphs have Hamiltonian cycles. I will tell a story (which is joint work with Balogh, Kostochka, and Liu) about why it’s important to have so many. This story leads to a class of hypergraphs that have more cycles than you ever thought possible (you may think of the hypergraphs as bipartite graphs if you prefer). I will discuss some results and conjectures (which are joint work with Kostochka, Luo, and Zirlin) about hypergraphs in this class.

Characteristic vectors of subsets of an \(n\)-element ground set give a natural 1-to-1 correspondence between set systems and 0-1 vector systems. As the size of the intersection of two sets equals the scalar product of their characteristic vectors, this correspondence is often used in proofs of intersection theorems of finite sets. There exist several definitions of intersection for vectors of length \(n\) with entries from \(\{0,1,...,q\}\). In this talk, we will propose a new one: the size of the \(s\)-sum intersection of two such vectors \(u,v\) is the number of coordinates where the entries have sum at least \(s\), i.e. \(|\{i: u_i+v_i\ge s\}|\). We address analogs of the following classical results in this setting: the Erdős–Ko–Rado theorem and the theorem of Bollobás on intersecting set pairs. We will also define an \(s\)-sum analog of graph Turán problems and survey results concerning them.

Joint work with Zsolt Tuza and Máté Vizer.

A central open problem in Ramsey theory is to determine the behavior of \(r_3(t)\), the minimum n such that any 2-coloring of the complete 3-uniform hypergraph on \(n\) vertices contains a monochromatic complete subgraph on \(t\) vertices. In the 1960’s, Erdős, Hajnal, and Rado showed that \(r_3(t)\) is bounded between exponential and double-exponential in \(t\), but the correct behavior remains unknown. Erdős and Hajnal surprisingly showed that the double-exponential bound is correct if we use four colors instead of two. This raises the question: how does the number of colors influence the growth of the Ramsey number? Generalizing a result of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower gaps between the 2-color and \(q\)-color Ramsey numbers. We utilize results analogous to the Erdős-Hajnal stepping-up lemma, for Ramsey numbers where we relax the "monochromatic" condition to "spanning few colors." Joint work with Quentin Dubroff, António Girão, and Eoin Hurley.

We formulate and prove matroid analogues of results concerning matchings in groups. A matching in an abelian group \((G,+)\) is a bijection \(f:A\to B\) between two finite subsets \(A,B\) of \(G\) satisfying \(a+f(a)\notin A\) for all \(a\in A\). A group \(G\) has the matching property if for every two finite subsets \(A,B \subset G\) of the same size with \(0 \notin B\), there exists a matching from \(A\) to \(B\). It is proved that an abelian group has the matching property if and only if it is torsion-free or cyclic of prime order. Here we consider a similar question in a matroid setting. We introduce an analogous notion of matching between matroids whose ground sets are subsets of an abelian group \(G\), and we obtain criteria for the existence of such matchings. This is joint work with Shira Zerbib.

The Borsuk-Ulam theorem from topology has many applications in discrete math. Necklace splitting, the ham sandwich theorem, Sperner’s lemma, fractional chromatic number bounds all follow from Borsuk-Ulam. By proving a colorful version of Ky-Fan’s Lemma, an analog of Borsuk-Ulam, we prove colorful generalizations of all of the applications of Borsuk-Ulam. By developing a single topological tool we get a wide variety of combinatorial results. This is joint work with Florian Frick (Carnegie Mellon University).

A sign pattern is a \((1,-1,0)\)-matrix. The entries of a sign pattern represent positive, negative and 0 entries of a real matrix. The set of real matrices with entries that have the same sign as the corresponding entries of a sign pattern \(S\) is denoted \(\mathcal{Q}(S)\). A sign pattern \(S\) allows orthogonality if there exists a row orthogonal matrix in \(\mathcal{Q}(S)\).The strong inner product property (SIPP) was developed by Curtis to study sign patterns of row orthogonal matrices. We further develop this theory. In particular, we introduce new results related to sign patterns that require the SIPP and minimally allow orthogonality. We also consider the behavior of random sign patterns that allow orthogonality.

Consider the following variant of Rock, Paper, Scissors (RPS) played by two players Rei and Norman. The game consists of \(3n\) rounds of RPS, with the twist being that Rei (the restricted player) must use each of Rock, Paper, and Scissors exactly \(n\) times during the \(3n\) rounds, while Norman is allowed to play normally without any restrictions. We show that a certain greedy strategy is the unique optimal strategy for Rei in this game, and that Norman’s expected score is \(\Theta(\sqrt{n})\). We also prove several general theorems about semi-restricted games arising from digraphs. This is joint work with Erlang Surya, Yuanfan Wang, Ji Zeng.

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.