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 Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k≥4 where n≥5 or k≥5, we prove that Sk(n)=2tk−1(n), where tk−1(n) is the number of edges of the n-vertex (k−1)-partite Turán graph Tk−1(n), and that Tk−1(n) is the only n-vertex graph with this number of orientations. Furthermore, S4(4)=40 and this maximality is achieved only by K4.
Given a family of graphs F, we prove that the normalized edit distance of any given graph Γ to being induced F-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan Regularity Lemma and on a Removal Lemma for F.
In this note, we adapt the Keevash-Sudakov proof of the (Turán) Stability Theorem for the Fano plane to find an explicit dependency between the parameters ε and δ. This is useful in the solution of a multicolored version for hypergraphs of an extremal problem about edge-colorings, known as the Erdős-Rothschild problem, which may be considered for the Fano plane.
The aim of this paper is to analyse the evolution of the COVID-19 pandemic in Rio Grande do Sul by applying graph-theoretical tools, particularly spectral clustering techniques, on weighted graphs defined on the set of 167 municipalities in the state with population 10,000 or more, which are based on data provided by government agencies and other sources. To respond to this outbreak, the state has adopted a system by which pre-determined regions are assigned flags on a weekly basis, and different measures go into effect according to the flag assigned. Our results suggest that considering a flexible approach to the regions themselves might be a useful additional tool to give more leeway to cities with lower incidence rates, while keeping the focus on public safety. Moreover, simulations show the dampening effect of isolation on the dissemination of the disease.
We find new upper bounds on the size of a minimum totally dominating set for random regular graphs and for regular graphs with large girth. These bounds are obtained through the analysis of a local algorithm using a method due to Hoppen and Wormald [Local algorithms, regular graphs of large girth, and random regular graphs. Combinatorica 38(3) (2018), 619-664].
The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It was recently proved that, for all n≥8, the balanced complete bipartite 3-uniform hypergraph on n vertices, denoted by Bn, is the 3-uniform hypergraph on n vertices with the largest number of hyperedges that does not contain a copy of the Fano plane. For sufficiently large r and n, we show that Bn admits the largest number of r-edge colorings with no rainbow copy of the Fano plane.
A generalized power hypergraph Hsk is obtained from a base hypergraph H by means of some simple edge-expansion operations. Kang, Liu, Qi and Yuan [8] proved that the nonzero eigenvalues of H give rise to nonzero eigenvalues of Hsk. In this paper we show that all nonzero eigenvalues of Hsk may be computed from the eigenvalues of its base hypergraph H and of its subgraphs. To prove this, we derive spectral results about edge-expansion operations that may be interesting on their own sake.
There has been substantial interest in estimating the value of a graph parameter, i.e., of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity qz=qz(ε) of an estimable parameter z is the size of a random sample of a graph G required to ensure that the value of z(G) may be estimated within an error of ε with probability at least 2/3. In this paper, for any fixed monotone graph property $\mathcal{P}=\mbox{Forb}(\mathcal{F})$, we study the sample complexity of estimating a bounded graph parameter zP that, for an input graph G, counts the number of spanning subgraphs of G that satisfy P. To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property P may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of P. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.
A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.
Given a graph F and an integer r≥2, a partition F of the edge set of F into at most r classes, and a graph G, define cr,F(G) as the number of r-colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F. We think of F as the pattern of coloring that should be avoided. The main question is, for a large enough n, to find the (extremal) graph G on n vertices which maximizes cr,F(G). This problem generalizes a question of Erd{\H o}s and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition F contains a single class). We use Hölder's Inequality together with Zykov's Symmetrization to prove that, for any r≥2, k≥3 and any pattern Kk of the clique Kk, there exists a complete multipartite graph that is extremal. Furthermore, if the pattern Kk has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r=3 and F is a rainbow triangle (that is, where F=K3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r=3, we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.
We investigate the problem of ordering trees according to their Laplacian energy. More precisely, given a positive integer n, we find a class of cardinality approximately n whose elements are the n-vertex trees with largest Laplacian energy. The main tool for establishing this result is a new upper bound on the sum Sk(T) of the k largest Laplacian eigenvalues of an n-vertex tree T with diameter at least four, where k∈{1,...,n}.
A permutation sequence is said to be convergent if the density of occurrences of every fixed permutation in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function Z:[0,1]2→[0,1] with the additional properties that, for every fixed x∈[0,1], the restriction Z(x,⋅) is a cumulative distribution function and, for every y∈[0,1], the restriction Z(⋅,y) satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An ingredient in the proofs is a new model of random permutations, which generalizes previous models and might be interesting for its own sake.
For fixed positive integers r,k and ℓ with 1≤ℓ<r and an r-uniform hypergraph H, let κ(H,k,ℓ) denote the number of k-colorings of the set of hyperedges of H for which any two hyperedges in the same color class intersect in at least ℓ elements. Consider the function $\KC(n,r,k,\ell)=\max_{H\in{\mathcal H}_{n}} κ(H, k,\ell) $, where the maximum runs over the family Hn of all r-uniform hypergraphs on n vertices. In this paper, we determine the asymptotic behavior of the function $\KC(n,r,k,\ell)$ for every fixed r, k and ℓ and describe the extremal hypergraphs. This variant of a problem of Erdős and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erdős--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {\bf 12} (1961), 313--320].
A permutation sequence (σn)n∈N is said to be convergent if, for every fixed permutation τ, the density of occurrences of τ in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function Z:[0,1]2→[0,1] with the additional properties that, for every fixed x∈[0,1], the restriction Z(x,⋅) is a cumulative distribution function and, for every y∈[0,1], the restriction Z(⋅,y) satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An important ingredient in the proofs is a new model of random permutations, which generalizes previous models and is interesting for its own sake.
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.