We consider the existence and construction of \textit{biclique covers} of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The \textit{size} of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size $O(n\polylog n)$. This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz's problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (\textit{Forum Math. Sigma}, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size $O(n\log^3 n)$. This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (\textit{Discrete Comput. Geom.} 1994). Finally, we prove that there exists families of unit disk graphs on $n$ vertices that do not admit biclique coverings of size $o(n^{4/3})$, showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k =0 (bipartite graphs) and for k =1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b -matching.

Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for each natural number $k$, we seek a vertex ordering such every vertex can (weakly respectively strongly) reach in $k$ steps only few vertices with lower index in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in the structural and algorithmic graph theory. Recently, the first author together with McCarty and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in $\mathbb{R}^d$, such as homothets of a centrally symmetric compact convex object, or comparable axis-aligned boxes. In this paper, we prove upper and lower bounds for the $k$-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in $k$, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).

We study a natural generalization of the classical $\epsilon$-net problem (Haussler--Welzl 1987), which we call the "$\epsilon$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $\epsilon\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\epsilon$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\epsilon$-$t$-net of size $O(\frac{ (1+\log t)d}{\epsilon} \log \frac{1}{\epsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\epsilon})$-sized $\epsilon$-$t$-nets. We also present an explicit construction of $\epsilon$-$t$-nets (including $\epsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\epsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

For $n\geq s> r\geq 1$ and $k\geq 2$, write $n \rightarrow (s)_{k}^r$ if every hyperedge coloring with $k$ colors of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by M. Axenovich, A. Gyárfás, H. Liu, and D. Mubayi [ Discrete Math., 322 (2014), pp. 69--77] and P. Erdös, A. Hajnal, A. Máté, and R. Rado, [ Combinatorial set theory: Partition Relations for Cardinals, Elsevier, Amsterdam, 1984] we show that $if r \geq 3 and n \nrightarrow (s)_k^r, then 2^n \nrightarrow (s+1)_{k+3}^{r+1}.$ This improves some of the known lower bounds on multicolor hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of coloring all $r$-subsets of $V$ such that no hyperedge of size $\geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $\chi(H)$. In particular we show that this number is $O(\log^{(r-1)} (r \chi(H)) + r)$, where $\log^{y}$ is the $\log$ function applied $y$ times.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than$k$vertex-disjoint odd cycles, where$k$is any constant. Previously, polynomial-time algorithms were only known for$k=0$(bipartite graphs) and for$k=1$. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

We study a natural generalization of the classical $ε$-net problem (Haussler--Welzl 1987), which we call the "$ε$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $ε\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $εn$ contains a set in $S$. When $t=1$, this corresponds to the $ε$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $ε$-$t$-net of size $O(\frac{ (1+\log t)d}ε \log \frac{1}ε)$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}ε)$-sized $ε$-$t$-nets. We also present an explicit construction of $ε$-$t$-nets (including $ε$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $ε$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ( \(n\rightarrow \infty \) ). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.