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
For a graph G, let τ(G) be the maximum number of colors such that there exists an edge-coloring of G with no two color classes being isomorphic. We investigate the behavior of τ(G) when G=G(n,p) is the classical Erdős-Rényi random graph.
We discuss the differential equation method for establishing dynamic concentration of discrete random processes. We present several relatively simple examples of it and aim to make the method understandable to the unfamiliar reader who has some basic knowledge on probabilistic methods, random graphs and differential equations.
We estimate the likely values of the chromatic and independence numbers of the random r-uniform d-regular hypergraph on n vertices for fixed r, large fixed d, and n→∞.
A (4,5)-coloring of Kn is an edge-coloring of Kn where every 4-clique spans at least five colors. We show that there exist (4,5)-colorings of Kn using 65n+o(n) colors. This settles a disagreement between Erdős and Gyárfás reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollobás and Erdős, and analyzed by Bohman, Frieze and Lubetzky.
A permutation in a digraph G=(V,E) is a bijection f:V→V such that for all v∈V we either have that f fixes v or (v,f(v))∈E. A derangement in G is a permutation that does not fix any vertex. In [1] it is proved that in any digraph, the ratio of derangements to permutations is at most 1/2. Answering a question posed in [1], we show that the set of possible ratios of derangements to permutations in digraphs is dense in the interval [0,1/2].
A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number τ(G) is at most twice the triangle packing number ν(G), where the triangle packing number ν(G) is the maximum size of a set of edge-disjoint triangles in G and the triangle covering number τ(G) is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erdős-Rényi random graph G(n,m) for all range of m, closing the gap in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in G(n,m) and analyze this process by using the differential equations method.
The triangle packing number ν(G) of a graph G is the maximum size of a set of edge-disjoint triangles in G. Tuza conjectured that in any graph G there exists a set of at most 2ν(G) edges intersecting every triangle in G. We show that Tuza's conjecture holds in the random graph G=G(n,m), when m≤0.2403n3/2 or m≥2.1243n3/2. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.
In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. Bennett, Dudek, and LaForge framed a variation of this problem in the language of alternating paths in edge-colored complete bipartite graphs in 2016. Here, we extend this problem to the random graph G(n,p). We seek the alternating connectivity, κr,ℓ(G), which is the maximum t such that there is an r-edge-coloring of G such that any pair of vertices is connected by t internally disjoint and alternating (i.e. no consecutive edges of the same color) paths of length ℓ. We have three main results about how this parameter behaves in G(n,p) that basically cover all ranges of p: one for paths of length two, one for the dense case, and one for the sparse case. For paths of length two, we found that κr,ℓ(G) is essentially the codegree of a pair of vertices. For the dense case when p is constant, we were able to achieve the natural upper bounds of minimum degree (minus some intersection) or the total number of disjoint paths between a pair of vertices. For the sparse case, we were able to find colorings that achieved the natural obstructions of minimum degree or (in a slightly less precise result) the total number of paths of a certain length in a graph. We broke up this sparse case into ranges of p corresponding to when G(n,p) has diameter k or k+1. We close with some remarks about a similar parameter and a generalization to pseudorandom graphs.
Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size (1−k1)(2n), where k≥3 is an integer, contains at least (101−2k1+k21−k31+5k42)n5+o(n5) copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.
Let C⊆[r]m be a code such that any two words of C have Hamming distance at least t. It is not difficult to see that determining a code C with the maximum number of words is equivalent to finding the largest n such that there is an r-edge-coloring of Km,n with the property that any pair of vertices in the class of size n has at least t alternating paths (with adjacent edges having different colors) of length 2. In this paper we consider a more general problem from a slightly different direction. We are interested in finding maximum t such that there is an r-edge-coloring of Km,n such that any pair of vertices in class of size n is connected by t internally disjoint and alternating paths of length 2k. We also study a related problem in which we drop the assumption that paths are internally disjoint. Finally, we introduce a new concept, which we call alternating connectivity. Our proofs make use of random colorings combined with some integer programs.
Given a graph on n vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colours on the edges. Similarly (for even n) a rainbow perfect matching is a collection of n/2 independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least 1 (respectively, at least 2). More precisely, consider n points (i.e. vertices) chosen independently and uniformly at random from the unit d-dimensional cube for any fixed d≥2. Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the ℓp norm, for any fixed 1<p≤∞). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of ⌈Kn⌉ colours, where K=K(d) is a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least 1 must contain a rainbow perfect matching (for even n), and the first graph with minimum degree at least 2 must contain a rainbow Hamilton cycle.
Let s be an integer, f=f(n) a function, and H a graph. Define the Ramsey-Turán number RTs(n,H,f) as the maximum number of edges in an H-free graph G of order n with αs(G)<f, where αs(G) is the maximum number of vertices in a Ks-free induced subgraph of G. The Ramsey-Turán number attracted a considerable amount of attention and has been mainly studied for f not too much smaller than n. In this paper we consider RTs(n,Kt,nδ) for fixed δ<1. We show that for an arbitrarily small ε>0 and 1/2<δ<1, RTs(n,Ks+1,nδ)=Ω(n1+δ−ε) for all sufficiently large s. This is nearly optimal, since a trivial upper bound yields RTs(n,Ks+1,nδ)=O(n1+δ). Furthermore, the range of δ is as large as possible. We also consider more general cases and find bounds on RTs(n,Ks+r,nδ) for fixed r≥2. Finally, we discuss a phase transition of RTs(n,K2s+1,f) extending some recent result of Balogh, Hu and Simonovits.
We investigate the space complexity of refuting 3-CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random 3-CNF ϕ in n variables requires, with high probability, Ω(n) distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation ϕ requires, with high probability, Ω(n) clauses each of width Ω(n) to be kept at the same time in memory. This gives a Ω(n2) lower bound for the total space needed in Resolution to refute ϕ. These results are best possible (up to a constant factor). The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2−ε), for ε<1/23.
Let G be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex u can be moved to a neighbouring vertex v, provided that the weight on v is at least as large as the weight on u. The total acquisition number of G, denoted by at(G), is the minimum possible size of the set of vertices with positive weight at the end of the process. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of p=p(n) such that at(G(n,p))=1 with high probability, where G(n,p) is a binomial random graph. We show that p=nlog2n≈1.4427 nlogn is a sharp threshold for this property. We also show that almost all trees T satisfy at(T)=Θ(n), confirming a conjecture of West.
Given an r-uniform hypergraph H=(V,E) and a weight function ω:E→{1,…,w}, a coloring of vertices of H, induced by ω, is defined by c(v)=∑e∋vw(e) for all v∈V. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that H is strongly w-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that H is weakly w-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all 5-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for r≥6 we show that almost all r-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for r≥4 almost all r-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are r-uniform hypergraphs which are not strongly (r2−r)-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.
We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let G(n,m) be a graph with m edges obtained after m steps of this process. Each edge ei (i=1,2,...,m) of G(n,m) independently chooses precisely k∈N colours, uniformly at random, from a given set of n−1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n,M) is connected and every colour occurs at least once (M=(2n) if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether G(n,M) has a rainbow spanning tree (that is, multicoloured tree on n vertices). Clearly, both properties are necessary for the desired tree to exist. In 1994, Frieze and McKay investigated the case k=1 and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is 2nlogn and the sharp threshold for seeing all the colours is knlogn, the case k=2 is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for k≥2.
We consider the Erdős-Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let D(n,m) be a graph with m edges obtained after m steps of this process. Each edge ei (i=1,2,…,m) of D(n,m) independently chooses a colour, taken uniformly at random from a given set of n(1+O(loglogn/logn))=n(1+o(1)) colours. We stop the process prematurely at time M when the following two events hold: D(n,M) has at most one vertex that has in-degree zero and there are at least n−1 distinct colours introduced (M=n(n−1) if at the time when all edges are present there are still less than n−1 colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether D(n,M) has a rainbow arborescence (that is, a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".
Nanomagnetic logic is an energy efficient computing architecture that relies on the dipole field coupling of neighboring magnets to transmit and process binary information. In this architecture, nanomagnet chains act as local interconnects. To assess the merits of this technology, the speed and reliability of magnetic signal transmission along these chains must be experimentally determined. In this work, time-resolved pump-probe x-ray photo-emission electron microscopy is used to observe magnetic signal transmission along a chain of nanomagnets. We resolve successive error-free switching events in a single nanomagnet chain at speeds on the order of 100 ps per nanomagnet, consistent with predictions based on micromagnetic modeling. Errors which disrupt transmission are also observed. We discuss the nature of these errors, and approaches for achieving reliable operation.
Energy efficient nanomagnetic logic (NML) computing architectures propagate and process binary information by relying on dipolar field coupling to reorient closely-spaced nanoscale magnets. Signal propagation in nanomagnet chains of various sizes, shapes, and magnetic orientations has been previously characterized by static magnetic imaging experiments with low-speed adiabatic operation; however the mechanisms which determine the final state and their reproducibility over millions of cycles in high-speed operation (sub-ns time scale) have yet to be experimentally investigated. Monitoring NML operation at its ultimate intrinsic speed reveals features undetectable by conventional static imaging including individual nanomagnetic switching events and systematic error nucleation during signal propagation. Here, we present a new study of NML operation in a high speed regime at fast repetition rates. We perform direct imaging of digital signal propagation in permalloy nanomagnet chains with varying degrees of shape-engineered biaxial anisotropy using full-field magnetic soft x-ray transmission microscopy after applying single nanosecond magnetic field pulses. Further, we use time-resolved magnetic photo-emission electron microscopy to evaluate the sub-nanosecond dipolar coupling signal propagation dynamics in optimized chains with 100 ps time resolution as they are cycled with nanosecond field pulses at a rate of 3 MHz. An intrinsic switching time of 100 ps per magnet is observed. These experiments, and accompanying macro-spin and micromagnetic simulations, reveal the underlying physics of NML architectures repetitively operated on nanosecond timescales and identify relevant engineering parameters to optimize performance and reliability.
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U and this is at least $n-\k(U)$ where n is the number of vertices of G and $\k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm \textsc{2greedy} for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching U with $\k(U) = \tildeΘ\of{n^{1/5}}$.
A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (2[k]) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ2(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for p≥Cn−1/4ln9/4n, τ2(Gn,p)=(2+o(1))χ(Gn,p) where χ represents the ordinary chromatic number. For sparse random graphs with p=c/n, c constant, we prove that τ2(Gn,p)=⌈8Δ+1+5/2⌉ where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.
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.