An official website of the United States government
Let $$H$$ and $$F$$ be hypergraphs. We say $$H$$ {\em contains $$F$$ as a trace} if there exists some set $$S \subseteq V(H)$$ such that $$H|_S:=\{E\cap S: E \in E(H)\}$$ contains a subhypergraph isomorphic to $$F$$. In this paper we give an upper bound on the number of edges in a $$3$$-uniform hypergraph that does not contain $$K_{2,t}$$ as a trace when $$t$$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $$\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$$.
more »
« less
Monochromatic Subgraphs in Iterated Triangulations
For integers $$n\ge 0$$, an iterated triangulation $$\mathrm{Tr}(n)$$ is defined recursively as follows: $$\mathrm{Tr}(0)$$ is the plane triangulation on three vertices and, for $$n\ge 1$$, $$\mathrm{Tr}(n)$$ is the plane triangulation obtained from the plane triangulation $$\mathrm{Tr}(n-1)$$ by, for each inner face $$F$$ of $$\mathrm{Tr}(n-1)$$, adding inside $$F$$ a new vertex and three edges joining this new vertex to the three vertices incident with $$F$$. In this paper, we show that there exists a 2-edge-coloring of $$\mathrm{Tr}(n)$$ such that $$\mathrm{Tr}(n)$$ contains no monochromatic copy of the cycle $$C_k$$ for any $$k\ge 5$$. As a consequence, the answer to one of two questions asked by Axenovich et al. is negative. We also determine the radius 2 graphs $$H$$ for which there exists $$n$$ such that every 2-edge-coloring of $$\mathrm{Tr}(n)$$ contains a monochromatic copy of $$H$$, extending a result of Axenovich et al. for radius 2 trees.
more »
« less
- Award ID(s):
- 1954134
- PAR ID:
- 10220444
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 27
- Issue:
- 4
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy.more » « less
-
null (Ed.)We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars.more » « less
-
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs areequivalentif there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number redge(H; q) of an edge‐ordered graphHis the smallestNsuch that there exists an edge‐ordered graphGonNvertices such that, for everyq‐coloring of the edges ofG, there is a monochromatic subgraph ofGequivalent toH. Recently, Balko and Vizer proved thatredge(H; q) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantcsuch thatfor every edge‐ordered graphHonnvertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.more » « less
-
Vizing’s celebrated theorem asserts that any graph of maximum degree ∆ admits an edge coloring using at most ∆ + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2∆−1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to lowdegree graphs, with ∆ = O(log n), and they conjectured the existence of online algorithms using ∆(1 + o(1)) colors for ∆ = ω(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS’03 and Bahmani et al., SODA’10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))∆-edge-coloring algorithm for ∆ = ω(log n) known a priori. Surprisingly, if ∆ is not known ahead of time, we show that no (e/(e−1)−Ω(1))∆-edge-coloring algorithm exists.We then provide an optimal, (e/(e−1) +o(1))∆-edge-coloring algorithm for unknown ∆ = ω(log n). Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/9292
