More Like this

1. A Structure Theorem for Pseudo-Segments and Its Applications

   https://doi.org/10.4230/LIPIcs.SoCG.2024.59  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   We prove a far-reaching strengthening of Szemerédi’s regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such graphs can be partitioned into a bounded number of parts of roughly the same size such that almost all of the bipartite graphs between pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every n-vertex simple topological graph with no k pairwise disjoint edges has at most n(log n)^O(log k) edges. 

   more » « less
2. Sharp bounds for decomposing graphs into edges and triangles

   https://doi.org/10.1017/S0963548320000358  

   Blumenthal, Adam; Lidický, Bernard; Pehova, Yanitsa; Pfender, Florian; Pikhurko, Oleg; Volec, Jan (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract For a real constant α , let $$\pi _3^\alpha (G)$$ be the minimum of twice the number of K 2 ’s plus α times the number of K 3 ’s over all edge decompositions of G into copies of K 2 and K 3 , where K r denotes the complete graph on r vertices. Let $$\pi _3^\alpha (n)$$ be the maximum of $$\pi _3^\alpha (G)$$ over all graphs G with n vertices. The extremal function $$\pi _3^3(n)$$ was first studied by Győri and Tuza ( Studia Sci. Math. Hungar. 22 (1987) 315–320). In recent progress on this problem, Král’, Lidický, Martins and Pehova ( Combin. Probab. Comput. 28 (2019) 465–472) proved via flag algebras that $$\pi _3^3(n) \le (1/2 + o(1)){n^2}$$ . We extend their result by determining the exact value of $$\pi _3^\alpha (n)$$ and the set of extremal graphs for all α and sufficiently large n . In particular, we show for α = 3 that K n and the complete bipartite graph $${K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil }}$$ are the only possible extremal examples for large n . 

   more » « less
3. 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
4. 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
5. A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.72  

   Enoch, Julian; Fox, Kyle; Mesica, Dor; Mozes, Shay (November 2021, 32nd International Symposium on Algorithms and Computation)

   Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.)

   We give an O(k³ Δ n log n min(k, log² n) log²(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of max(k²,k log² n) over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses O(k) invocations of an O(k³ n log³ n)-time algorithm for maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the k-apex graphs that arise in our modification of Wang’s procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan [JACM 1988]. 

   more » « less