Search

We prove an arithmetic analogue of the typical structure theorem for graph hereditary properties due to Alon, Balogh, Bollobás and Morris [2]. [ABSTRACT FROM AUTHOR]

The method of hypergraph containers, which was introduced several years ago by Balogh, Morris, and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the study of various monotone graph properties. In particular, a fairly straightforward application of this technique allows one to locate, for each non-bipartite graph H, the threshold at which the distribution of edges in a typical H-free graph with a given number of edges undergoes a transition from 'random-like' to 'structured'. On the other hand, for nonmonotone hereditary graph properties, the standard version of this method does not allow one to establish even the existence of such a threshold. In this paper we introduce a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. As an application, we determine the approximate structure of a typical graph with n vertices, m edges, and no induced copy of the 4-cycle, for each function m D m.n/ satisfying n4=3.log n/4 6 m n2. We show that almost all such graphs G have the following property: the vertex set of G can be partitioned into an 'almost independent' set (a set with o.m/ edges) and an 'almost-clique' (a set inducing a subgraph with density 1-a The lower bound on m is optimal up to a polylogarithmic factor, as standard arguments show that if n then almost all such graphs are 'random-like'. As a further consequence, we deduce that the random graph G.n; p/ conditioned to contain no induced 4-cycles undergoes phase transitions at p=n -2/3+o(1) p=n -2/3+o(1). [ABSTRACT FROM AUTHOR]

The present paper aims to investigate some semi-separation axioms relating to the Alexandroff one point compactification (Alexandroff compactification, for short) of the digital plane with the Marcus-Wyse ($ MW $-, for brevity) topology. The Alexandroff compactification of the $ MW $-topological plane is called the infinite $ MW $-topological sphere up to homeomorphism. We first prove that under the $ MW $-topology on $ {\mathbb Z}^2 $ the connectedness of $ X(\subset {\mathbb Z}^2) $ with $ X^\sharp\geq 2 $ implies the semi-openness of $ X $. Besides, for the infinite $ MW $-topological sphere, we introduce a new condition for the hereditary property of the compactness of it. In addition, we investigate some conditions preserving the semi-openness or semi-closedness of a subset of the $ MW $-topological plane in the process of an Alexandroff compactification. Finally, we prove that the infinite $ MW $-topological sphere is a semi-regular space; thus, it is a semi-$ T_3 $-space because it is a semi-$ T_1 $-space. Hence we finally conclude that an Alexandroff compactification of the $ MW $-topological plane preserves the semi-$ T_3 $ separation axiom.

The present paper aims to investigate some semi-separation axioms relating to the Alexandroff one point compactification (Alexandroff compactification, for short) of the digital plane with the Marcus-Wyse ( M W -, for brevity) topology. The Alexandroff compactification of the M W -topological plane is called the infinite M W -topological sphere up to homeomorphism. We first prove that under the M W -topology on Z 2 the connectedness of X (⊂ Z 2) with X ♯ ≥ 2 implies the semi-openness of X. Besides, for the infinite M W -topological sphere, we introduce a new condition for the hereditary property of the compactness of it. In addition, we investigate some conditions preserving the semi-openness or semi-closedness of a subset of the M W -topological plane in the process of an Alexandroff compactification. Finally, we prove that the infinite M W -topological sphere is a semi-regular space; thus, it is a semi- T 3 -space because it is a semi- T 1 -space. Hence we finally conclude that an Alexandroff compactification of the M W -topological plane preserves the semi- T 3 separation axiom. [ABSTRACT FROM AUTHOR]

The edit distance function of a hereditary property 𝒣 is the asymptotically largest edit distance between a graph of density p ∈ [0, 1] and 𝒣. Denote by Pn and Cn the path graph of order n and the cycle graph of order n, respectively. Let C2n*C_{2n}^* be the cycle graph C2n with a diagonal, and C˜n{\tilde C_n} be the graph with vertex set {v0, v1, . . . , vn−1} and E(C˜n)=E(Cn)∪{v0v2}E\left( {{{\tilde C}_n}} \right) = E\left( {{C_n}} \right) \cup \left\{ {{v_0}{v_2}} \right\}. Marchant and Thomason determined the edit distance function of C6*C_6^*. Peck studied the edit distance function of Cn, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of C8*C_8^*, C˜n{\tilde C_n} and Pn, respectively.

Let kk be a positive integer and let GG be a graph with vertex set V(G)V(G). A subset D⊆V(G)D\subseteq V(G) is a kk-dominating set if every vertex outside DD is adjacent to at least kk vertices in DD. The kk-domination number γk(G){\gamma }_{k}(G) is the minimum cardinality of a kk-dominating set in GG. For any graph GG, we know that γk(G)≥γ(G)+k−2{\gamma }_{k}(G)\ge \gamma (G)+k-2 where Δ(G)≥k≥2\text{Δ}(G)\ge k\ge 2 and this bound is sharp for every k≥2k\ge 2. In this paper, we characterize bipartite graphs satisfying the equality for k≥3k\ge 3 and present a necessary and sufficient condition for a bipartite graph to satisfy the equality hereditarily when k=3k=3. We also prove that the problem of deciding whether a graph satisfies the given equality is NP-hard in general.

Motivated by many practical applications, in this paper we study budget feasible mechanisms with the goal of procuring an independent set of a matroid. More specifically, we are given a matroid M = (E , I) . Each element of the ground set E is controlled by a selfish agent and the cost of the element is private information of the agent itself. A budget limited buyer has additive valuations over the elements of E. The goal is to design an incentive compatible budget feasible mechanism which procures an independent set of the matroid of largest possible value. We also consider the more general case of the pair M = (E , I) satisfying only the hereditary property. This includes matroids as well as matroid intersection. We show that, given a polynomial time deterministic algorithm that returns an α -approximation to the problem of finding a maximum-value independent set in M , there exists an individually rational, truthful and budget feasible mechanism which is (3 α + 1) -approximated and runs in polynomial time, thus yielding also a 4-approximation for the special case of matroids. [ABSTRACT FROM AUTHOR]

Balogh, Bollobás and Weinreich showed that a parameter that has since been termed the distinguishing number can be used to identify a jump in the possible speeds of hereditary classes of graphs at the sequence of Bell numbers. We prove that every hereditary class that lies above the Bell numbers and has finite distinguishing number contains a boundary class for well‐quasi‐ordering. This means that any such hereditary class which in addition is defined by finitely many minimal forbidden induced subgraphs must contain an infinite antichain. As all hereditary classes below the Bell numbers are well‐quasi‐ordered, our results complete the answer to the question of well‐quasi‐ordering for hereditary classes with finite distinguishing number. We also show that the decision procedure of Atminas, Collins, Foniok and Lozin to decide the Bell number (and which now also decides well‐quasi‐ordering for classes of finite distinguishing number) has runtime bounded by an explicit (quadruple exponential) function of the order of the largest minimal forbidden induced subgraph of the class. [ABSTRACT FROM AUTHOR]

The edit distance function of a hereditary property H is the asymptotically largest edit distance between a graph of density p ∈ [0, 1] and H . Denote by Pn and Cn the path graph of order n and the cycle graph of order n, respectively. Let C*2n be the cycle graph C2n with a diagonal, and fCn be the graph with vertex set {v0, v1, . . . , vn−1} and E(Cn) = E(Cn) ∪ {v0v2}. Marchant and Thomason determined the edit distance function of C*6. Peck studied the edit distance function of Cn, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of C*8, Cn and Pn, respectively. [ABSTRACT FROM AUTHOR]

While topology given by a linear order has been extensively studied, this cannot be said about the case when the order is given only locally. The aim of this paper is to fill this gap. We consider relation between local orderability and separation axioms and give characterisation of those regularly locally ordered spaces which are connected, locally connected or Lindelöf. We prove that local orderability is hereditary on open, connected or compact subsets. A collection of interesting examples is also offered. [ABSTRACT FROM AUTHOR]

In breakthrough results, Saxton‐Thomason and Balogh‐Morris‐Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simple container theorem of Saxton‐Thomason and an entropy‐based framework to deduce container and counting theorems for hereditary properties of k‐colorings of very general objects, which include both vertex‐ and edge‐colorings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterization and transference results for hereditary properties in terms of their stability families and extremal entropy. This covers within a unified framework a great variety of combinatorial structures, some of which had not previously been studied via containers: directed graphs, oriented graphs, tournaments, multigraphs with bounded multiplicity, and multicolored graphs among others. Similar results were recently and independently obtained by Terry. [ABSTRACT FROM AUTHOR]

The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible.

Abstract Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete. [ABSTRACT FROM AUTHOR]

We study a hereditary starlikeness property for planar harmonic mappings on a disk and on an annulus. While such a property is a common trait of conformal mappings, it may be absent in harmonic mappings. It turns out that a sufficient condition for a harmonic mapping f to possess this hereditary property is to have a harmonic argument — a striking feature of conformal mappings that does not extend to all harmonic mappings. [ABSTRACT FROM AUTHOR]

Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P. We prove that, for every fixed p ∈ (0 , 1) , the maximum possible number of edges in a subgraph of the random graph G (n , p) which belongs to P is, with high probability, (1 − 1 k − 1 + o (1)) p ( n 2 ). [ABSTRACT FROM AUTHOR]

A sum graph G is a graph with a mapping of the vertex set of G onto a set of positive integers S in such a way that two vertices of G are adjacent if and only if the sum of their labels is an element of S . In an exclusive sum graph the integers of S that are the sum of two other integers of S form a set of integers that label a collection of isolated vertices associated with the graph G . A graph bears a k-exclusive sum labelling (abbreviated k -ESL), if the set of isolated vertices is of cardinality k . In this paper, observing that the property of having a k -ESL is hereditary, we provide a characterisation of graphs that have a k -exclusive sum labelling, for any k ≥ 1 , in terms of describing a universal graph for the property. [ABSTRACT FROM AUTHOR]

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes. [ABSTRACT FROM AUTHOR]

In this paper1 we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance (a graph with n vertices) is revealed in t clusters, 2 ≤ t ≤ n . We first focus on an on-line version of the maximumweighted hereditary subgraph problem. Then, we deal with the particular case of the independent set problem. We are interested in two types of results: the competitive ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.

Given a hypergraph H = (X; ε), an integer k ≥ 1 and a property P, of subsets of X, a (P; k)-coloring of H is a function π : X → {1; 2; : : : ; k}=: k such that for all i ∈ k the induced subhypergraph (π-1(i)H ∈ P, where P denotes the set of all subsets of X that do not possess the property P. The hypergraph H is (P; k)-colorable if and only if it has a (P; k)-coloring. The P-chromatic number XP(H) of H is then defined as the least k such that H has a (P; k)-coloring. In this note, we initiate a study of XP(H) for hereditary properties P. For non-hereditary properties, the study appears challenging. [ABSTRACT FROM AUTHOR]

For a set of graphs Π , the Stable - Π problem asks whether, given a graph G , we can find an independent set S in G , such that G − S ∈ Π . For instance, if Π is the set of all bipartite graphs, Stable - Π coincides with vertex 3- colourability , and if Π is the set of 1-regular graphs, the problem is known as efficient edge domination . Numerous other examples of the Stable - Π problem have been studied in the literature. In the present contribution, we systematically study the Stable - Π problem with respect to the speed (a term meaning size) of Π . In particular, we show that for all hereditary classes Π with a subfactorial speed of growth, Stable - Π is solvable in polynomial time. We then explore the problem for minimal hereditary factorial classes Π . Contrary to the conjecture proposed in Lozin (2005) [18] , the complexity of Stable - Π turns out to be polynomial for nearly all minimal hereditary factorial classes Π . On the other hand, if we do not require Π to be hereditary, the complexity of the problem can jump to NP-completeness. [ABSTRACT FROM AUTHOR]

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The edit distance function of the hereditary property, H , is a function of p ∈ [ 0 , 1 ] and is the limit of the maximum normalized distance between a graph of density p and H . This paper uses the symmetrization method of Sidorenko in order to compute the edit distance function of various hereditary properties. For any graph H , Forb ( H ) denotes the property of not having an induced copy of H . We compute the edit distance function for Forb ( H ) , where H is any split graph, and the graph H 9 , a graph first used to describe the difficulties in computing the edit distance function. [ABSTRACT FROM AUTHOR]