More Like this

1. A discrepancy version of the Hajnal–Szemerédi theorem

   https://doi.org/10.1017/S0963548320000516  

   Balogh, József; Csaba, Béla; Pluhár, András; Treglown, Andrew (May 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract A perfect K r -tiling in a graph G is a collection of vertex-disjoint copies of the clique K r in G covering every vertex of G . The famous Hajnal–Szemerédi theorem determines the minimum degree threshold for forcing a perfect K r -tiling in a graph G . The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph G labels from {‒1, 1}, and one seeks substructures F of G that have ‘high’ discrepancy ( i.e. the sum of the labels of the edges in F is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect K r -tiling of high discrepancy. 

   more » « less
2. Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

   https://doi.org/10.1017/S0963548320000061  

   Falgas-Ravry, Victor; Markström, Klas; Zhao, Yi (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

   more » « less
3. Optimal Bounds for the k -cut Problem

   https://doi.org/10.1145/3478018  

   Gupta, Anupam; Harris, David G.; Lee, Euiwoong; Li, Jason (February 2022, Journal of the ACM)

   In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that Ω ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight α λ k with probability Ω k ( n - α k ), where λ k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute λ k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λ k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process. 

   more » « less
4. A completion of the proof of the Edge-statistics Conjecture

   https://doi.org/10.19086/aic.12047  

   Fox, Jacob; Sauermann, Lisa (February 2020, Advances in Combinatorics)

   Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $$H$$ in an $$n$$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $$H$$ and the number of all subgraphs with the same number vertices as $$H$$; this quantity is known as the _inducibility_ of $$H$$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $$k$$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $$k$$ vertices be? Fix $$k$$, consider a graph with $$n$$ vertices join each pair of vertices independently by an edge with probability $$\binom{k}{2}^{-1}$$. The expected number of $$k$$-vertex induced subgraphs with exactly one edge is $$e^{-1}+o(1)$$. So, the inducibility of large graphs with a single edge is at least $$e^{-1}+o(1)$$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $$k$$-vertex graphs with exactly $$l$$ edges where $$0<\binom{k}{2}$$ is at most $$e^{-1}+o(1)$$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $$l$$ is superlinearly bounded away from $$0$$ and $$\binom{k}{2}$$, for which the sum of the inducibilities goes to zero, and also in the regime where $$l$$ is bounded away from $$0$$ and $$\binom{k}{2}$$ by a sufficiently large linear function. The article resolves the hardest cases where $$l$$ is linearly close to $$0$$ or close to $$\binom{k}{2}$$, and provides generalizations to hypergraphs. 

   more » « less
5. Failed zero forcing and critical sets on directed graphs

   Adams, Alyssa; Jacob, Bonnie (October 2021, The Australasian journal of combinatorics)

   Let $$D$$ be a simple digraph (directed graph) with vertex set $V(D)$ and arc set $A(D)$ where $n=|V(D)|$, and each arc is an ordered pair of distinct vertices. If $$(v,u) \in A(D)$$, then $$u$$ is considered an \emph{out-neighbor} of $$v$$ in $$D$$. Initially, we designate each vertex to be either filled or empty. Then, the following color change rule (CCR) is applied: if a filled vertex $$v$$ has exactly one empty out-neighbor $$u$$, then $$u$$ will be filled. If all vertices in $V(D)$$ are eventually filled under repeated applications of the CCR, then the initial set is called a \emph{zero forcing set} (ZFS); if not, it is a \emph{failed zero forcing set} (FZFS). We introduce the \emph{failed zero forcing number} $$\F(D)$$ on a digraph, which is the maximum cardinality of any FZFS. The \emph{zero forcing number}, $$\Z(D)$, is the minimum cardinality of any ZFS. We characterize digraphs that have $$\F(D)<\Z(D)$$ and determine $$\F(D)$$ for several classes of digraphs including de Bruijn and Kautz digraphs. We also characterize digraphs with $$\F(D)=n-1$$, $$\F(D)=n-2$$, and $$\F(D)=0$$, which leads to a characterization of digraphs in which any vertex is a ZFS. Finally, we show that for any integer $$n \geq 3$$ and any non-negative integer $$k$$ with $k 

   more » « less