A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

Dimension-2 poset competition numbers and dimension-2 poset double competition numbers

Let D=(V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set . The double competition graph of D, is the graph with vertex set V(D) and edge set . A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R² and there is an arc going from a vertex (x₁,y₁) to a vertex (x₂,y₂) if and only if x₁>x₂ and y₁>y₂. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.     

On the transversal number and VC-dimension of families of positive homothets of a convex body

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180]. Our bound is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166-2173], which was of order nⁿ. By a lower bound, we show that the right order of magnitude is exponential in n.Next, we consider another measure of complexity, the Vapnik-?ervonenkis dimension of F. We prove that vcdim(F)≤3 if n=2 and is infinite for some F if n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12-23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rⁿ is n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101-105] who constructed a counterexample of dual VC-dimension . Our result implies that no upper bound exists.     

Weighted covering numbers of convex sets

In this paper we define the notions of weighted covering number and weighted separation number for convex sets, and compare them to the classical covering and separation numbers. This sheds new light on the equivalence of classical covering and separation. We also provide a formula for computing these numbers via a limit of classical covering numbers in higher dimensions.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

Characterizations of Hermitian varieties by intersection numbers

In this paper, we give characterizations of the classical generalized quadrangles H(3, q ²) and H(4, q ²), embedded in PG(3, q ²) and PG(4, q ²), respectively. The intersection numbers with lines and planes characterize H(3, q ²), and H(4, q ²) is characterized by its intersection numbers with planes and solids. This result is then extended to characterize all Hermitian varieties in dimension at least 4 by their intersection numbers with planes and solids.      

Proof of a conjecture on fractional Ramsey numbers

Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function r_f (a₁, a₂, …, a_k) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010     

Multichromatic numbers,star chromatic numbers and Kneser graphs

We investigate the relation between the multichromatic number (discussed by Stahl and by Hilton, Rado and Scott) and the star chromatic number (introduced by Vince) of a graph. Denoting these by χ* and η*, the work of the above authors shows that χ*(G) = η*(G) if G is bipartite, an odd cycle or a complete graph. We show that χ*(G) ≤ η*(G) for any finite simple graph G. We consider the Kneser graphs , for which χ* = m/n and η*(G)/χ*(G) is unbounded above. We investigate particular classes of these graphs and show that η* = 3 and η* = 4; (n ≥ 1), and η* = m - 2; (m ≥ 4). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 137–145, 1997     

Fully gated graphs: Recognition and convex operations

A graph is fully gated when every convex set of vertices is gated. Doignon posed the problem of characterizing fully gated graphs and in particular of deciding whether there is an efficient algorithm for their recognition. While the number of convex sets can be exponential, we establish that it suffices to examine only the convex hulls of pairs of vertices. This yields an elementary polynomial time algorithm for the recognition of fully gated graphs; however, it does not appear to lead to a simple structural characterization. In this direction, we establish that fully gated graphs are closed under a set of ‘convex’ operations, including a new operation which duplicates the vertices of a convex set (under some well-defined restrictions). This in turn establishes that every bipartite graph is an isometric subgraph of a fully gated graph, thereby severely limiting the potential for a characterization based on subgraphs. Finally, a large class of fully gated graphs is obtained using the presence of bipartite dominators, which suggests that simple convex operations cannot suffice to produce all fully gated graphs.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Local and union boxicity

The boxicity $box\left(H\right)$ of a graph $H$ is the smallest integer $d$ such that $H$ is the intersection of $d$ interval graphs, or equivalently, that $H$ is the intersection graph of axis-aligned boxes in ${\mathbb{R}}^d$. These intersection representations can be interpreted as covering representations of the complement $H^c$ of $H$ with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity ${box}_{?}\left(H\right)$ and the union boxicity $\overline{box}\left(H\right)$ of $H$. The union boxicity of $H$ is the smallest $d$ such that $H^c$ can be covered with $d$ vertex–disjoint unions of co-interval graphs, while the local boxicity of $H$ is the smallest $d$ such that $H^c$ can be covered with co-interval graphs, at most $d$ at every vertex.We show that for every graph $H$ we have ${box}_{?}\left(H\right)\le \overline{box}\left(H\right)\le box\left(H\right)$ and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in ${\mathbb{R}}^d$. We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

Spectral strengthening of a theorem on transversal critical graphs

A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by $\tau (G)$, is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if $\tau (G?e)<\tau (G)$ for every edge $e\in E(G)$. For any τ-critical graph G with $\tau (G)=t$, it has been shown that $|V(G)|\le 2t$ by Erd?s and Gallai and that $|E(G)|\le \left(\begin{array}{c}t+1\\ 2\end{array}\right)$ by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to $|V(G)|+|E(G)|\le \left(\begin{array}{c}t+2\\ 2\end{array}\right)$. In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with $\tau (G)=t$ and $|V(G)|=n$, and let ${\lambda }_1$ denote the largest eigenvalue of the adjacency matrix of G. We show that $n+{\lambda }_1\le 2t+1$ with equality if and only if G is $t{K}_2$, $K_{s+1}\cup (t?s)K_2$, or $C_{2s?1}\cup (t?s)K_2$, where $2\le s\le t$; and in particular, ${\lambda }_1(G)\le t$ with equality if and only if G is $K_{t+1}$. We then apply it to show that for any nonnegative integer r, we have $n(r+\frac{{\lambda }_1}{2})\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$ and characterize all extremal graphs. This implies a pure combinatorial result that $r|V(G)|+|E(G)|\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$, which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Asymptotic shape of a random polytope in a convex body

Let K be an isotropic convex body in and let Z_q(K) be the L_q-centroid body of K. For every N>n consider the random polytope K_N:=conv{x₁,…,x_N} where x₁,…,x_N are independent random points, uniformly distributed in K. We prove that a random K_N is “asymptotically equivalent” to Z_[ln(N/n)](K) in the following sense: there exist absolute constants ρ₁,ρ₂>0 such that, for all and all NN(n,β), one has:

(i) K_Nc(β)Z_q(K) for every qρ₁ln(N/n), with probability greater than 1−c₁exp(−c₂N^1−βn^β).

(ii) For every qρ₂ln(N/n), the expected mean width of K_N is bounded by c₃w(Z_q(K)).

As an application we show that the volume radius |K_N|^1/n of a random K_N satisfies the bounds for all Nexp(n).

Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

The biplanar crossing number cr₂(G) of a graph G is min{cr(G₁) + cr(G₂)}, where cr is the planar crossing number. We show that cr₂(G) ≤ (3/8)cr(G). Using this result recursively, we bound the thickness by Θ(G) ‐ 2 ≤ Kcr₂(G)^0.4057 log₂n with some constant K. A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph G of this size, which simultaneously has the following properties: cr(G) is roughly as large as it can be for any graph of that size, and cr₂(G) is as small as it can be for any graph of that size. The existence is shown using the probabilistic method. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Illumination by translates of convex sets

Let S be a compact set in the plane. If every three points of S are illuminated clearly by some translate of the compact convex set T, then there is a translate of T which illumines every point of S. Various analogues hold for translates of flats in R ^das well.Supported in part by NSF grant DMS-8705336.