Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of edges of separated multigraphs
73
0
0.0
(
0
)
Added by
Andrew Suk
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^2log n)$, provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in $G$ contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, if $G$ has $e geq 4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $Omegaleft(frac{e^3}{n^2log(e/n)}right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.
rate research
Read More
We prove a new upper bound on the number of $r$-rich lines (lines with at least $r$ points) in a `truly $d$-dimensional configuration of points $v_1,ldots,v_n in mathbb{C}^d$. More formally, we show that, if the number of $r$-rich lines is significantly larger than $n^2/r^d$ then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor $r^d$ can be replaced with a tight $r^{d+1}$. If true, this would generalize the classic Szemeredi-Trotter theorem which gives a bound of $n^2/r^3$ on the number of $r$-rich lines in a planar configuration. This conjecture was shown to hold in $mathbb{R}^3$ in the seminal work of Guth and Katz cite{GK10} and was also recently proved over $mathbb{R}^4$ (under some additional restrictions) cite{SS14}. For the special case of arithmetic progressions ($r$ collinear points that are evenly distanced) we give a bound that is tight up to low order terms, showing that a $d$-dimensional grid achieves the largest number of $r$-term progressions. The main ingredient in the proof is a new method to find a low degree polynomial that vanishes on many of the rich lines. Unlike previous applications of the polynomial method, we do not find this polynomial by interpolation. The starting observation is that the degree $r-2$ Veronese embedding takes $r$-collinear points to $r$ linearly dependent images. Hence, each collinear $r$-tuple of points, gives us a dependent $r$-tuple of images. We then use the design-matrix method of cite{BDWY12} to convert these local linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.
Given a multigraph $G=(V,E)$, the {em edge-coloring problem} (ECP) is to color the edges of $G$ with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is called the {em fractional edge-coloring problem} (FECP). In the literature, the optimal value of ECP (resp. FECP) is called the {em chromatic index} (resp. {em fractional chromatic index}) of $G$, denoted by $chi(G)$ (resp. $chi^*(G)$). Let $Delta(G)$ be the maximum degree of $G$ and let [Gamma(G)=max Big{frac{2|E(U)|}{|U|-1}:,, U subseteq V, ,, |U|ge 3 hskip 2mm {rm and hskip 2mm odd} Big},] where $E(U)$ is the set of all edges of $G$ with both ends in $U$. Clearly, $max{Delta(G), , lceil Gamma(G) rceil }$ is a lower bound for $chi(G)$. As shown by Seymour, $chi^*(G)=max{Delta(G), , Gamma(G)}$. In the 1970s Goldberg and Seymour independently conjectured that $chi(G) le max{Delta(G)+1, , lceil Gamma(G) rceil}$. Over the past four decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated a significant body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for $chi(G)$, so an analogue to Vizings theorem on edge-colorings of simple graphs, a fundamental result in graph theory, holds for multigraphs; second, although it is $NP$-hard in general to determine $chi(G)$, we can approximate it within one of its true value, and find it exactly in polynomial time when $Gamma(G)>Delta(G)$; third, every multigraph $G$ satisfies $chi(G)-chi^*(G) le 1$, so FECP has a fascinating integer rounding property.
An oriented k-uniform hypergraph (a family of ordered k-sets) has the ordering property (or Property O) if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. We find bounds on the minimum number of edges in a hypergraph with Property O.
A basic combinatorial invariant of a convex polytope $P$ is its $f$-vector $f(P)=(f_0,f_1,dots,f_{dim P-1})$, where $f_i$ is the number of $i$-dimensional faces of $P$. Steinitz characterized all possible $f$-vectors of $3$-polytopes and Grunbaum characterized the pairs given by the first two entries of the $f$-vectors of $4$-polytopes. In this paper, we characterize the pairs given by the first two entries of the $f$-vectors of $5$-polytopes. The same result was also proved by Pineda-Villavicencio, Ugon and Yost independently.
This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobas independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korandi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korandi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
