BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let r(k) denote the maximum number of edges in a k-uniform intersecting family with covering number k. Erdős and Lovász proved that ⌊k!(e−1)⌋≤r(k)≤kk. Frankl, Ota, and Tokushige improved the lower bound to r(k)≥(k/2)k−1, and Tuza improved the upper bound to r(k)≤(1−e−1+o(1))kk. We establish that r(k)≤(1+o(1))kk−1.
An edge-ordering of a graph G=(V,E) is a bijection ϕ:E→{1,2,...,∣E∣}. Given an edge-ordering, a sequence of edges P=e1,e2,...,ek is an increasing path if it is a path in G which satisfies ϕ(ei)<ϕ(ej) for all i<j. For a graph G, let f(G) be the largest integer ℓ such that every edge-ordering of G contains an increasing path of length ℓ. The parameter f(G) was first studied for G=Kn and has subsequently been studied for other families of graphs. This paper gives bounds on f for the hypercube and the random graph G(n,p).
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4.
Extending the concept of Ramsey numbers, Erd{\H o}s and Rogers introduced the following function. For given integers 2≤s<t let fs,t(n)=min{max{∣W∣:W⊆V(G)andG[W]containsnoKs}}, where the minimum is taken over all Kt-free graphs G of order n. In this paper, we show that for every s≥3 there exist constants c1=c1(s) and c2=c2(s) such that fs,s+1(n)≤c1(logn)c2n. This result is best possible up to a polylogarithmic factor. We also show for all t−2≥s≥4, there exists a constant c3 such that fs,t(n)≤c3n. In doing so, we partially answer a question of Erdős by showing that limn→∞fs,s+2(n)fs+1,s+2(n)=∞ for any s≥4.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.