Search

AbstractA sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed:1.If a FO-convergent sequence of graphs is residual, that is if for every integer dthe maximum relative size of a ball of radius din the graphs of the sequence tends to zero, then the sequence has a modeling limit.2.A monotone class of graphs ${\cal C}$has the property that every FO-convergent sequence of graphs from ${\cal C}$has a modeling limit if and only if ${\cal C}$is nowhere dense, that is if and only if for each integer pthere is $N\left( p \right)$such that no graph in ${\cal C}$contains the pth subdivision of a complete graph on $N\left( p \right)$vertices as a subgraph.In this article we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy.

A primary goal of current clinical cancer research is the identification of prognostic tumor subtypes. It is increasingly clear that tumor growth depends on both internal tumor factors, and factors that are external to the tumor, such as microenvironment. We recently showed that parameter values alone are less important than the patterns of all patient parameters together for the identification of prognostic subtypes and have identified a network phenotyping strategy method to quantitatively describe the dependency of the tumor on the environment, to characterize hepatocellular carcinoma (HCC) subtypes. We have also shown that information about tumor mass together with patterns of other prognostic factors is related to survival. We now use a different patient cohort to validate this prognostic approach. A main finding is our identification of a common time of total disease duration (TDD) for every HCC patient. Clinical prognosis at the time of baseline patient evaluation is then calculable as the difference between TDD and the time from disease onset to diagnosis (Tonset). We show that the total pattern of all parameter values and the differences in the relationships between this pattern and a reference pattern that, together with the tumor mass, best reflects the patient’s prognosis at baseline. Our approach led us to identify 15 different composite HCC subtypes. Our results highlight the nearly identical TDD in all patients, which must therefore be a characteristic of the HCC disease, as opposed to the variable quantity of Tonset, which is impacted by multiple macro- and micro-environmental factors.

The relational complexity, introduced by G. Cherlin, G. Martin, and D. Saracino, is a measure of ultrahomogeneity of a relational structure. It provides an information on minimal arity of additional invariant relations needed to turn given structure into an ultrahomogeneous one. The original motivation was group theory. This work focuses more on structures and provides an alternative approach. Our study is motivated by related concept of lift complexity studied by Hubička and Nešetřil.

Beck introduced the concept of Ramsey games by studying the game versions of Ramsey and van der Waerden theorems. We contribute to this topic by investigating games corresponding to structural extensions of Ramsey and van der Waerden theorems—the theorem of Brauer, structural and restricted Ramsey theorems. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 330–342, 2010

We investigate bounds on the chromatic number of a graph Gderived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document}into some orientation \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{G}\end{eqnarray*}\end{document}of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document}depends on the relation between the “algebraic length” and “derived algebraic length” of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document}. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 198–209, 2010

AbstractLet Tbe a Hamiltonian multipartite tournament with nvertices and γ a Hamiltonian cycle of T. We prove that for every k, 4 ≤ k≤ , there exists a cycle Cof length l(C) ∊ {k— 3, k– 2, k— 1, k}, whose intersection with the arcs of γ is at least l(C) – 3. In some cases the result is best possible.

A class of graphs ${\cal C}$ordered by the homomorphism relation is universalif every countable partial order can be embedded in ${\cal C}$. It is known (see [1,3]) that the class $\cal C_{k}$of k‐colorable graphs, for any fixed ${k}\geq 3 $, induces a universal partial order. In 4, a surprisingly small subclass of $\cal C_{3}$which is a proper subclass of the series‐parallel graphs (the K4‐minor‐free graphs) is shown to be universal. On another side, Pan and Zhu in 7 proved a density result that for each rational number ${a}/{b}\in [2,8/3]\cup\{3\} $, there is a K4‐minor‐free graph with circular chromatic number equal to a/b. In this note, we show for each rational number a/bwithin this interval the class $\cal K_{a/b} $of K4‐minor‐free graphs with circular chromatic number a/bis universal if and only if $ a/b\neq2 $, 5/2 or 3. This shows yet another surprising richness of the K4‐minor‐free class that it contains universal classes as dense as the rational numbers. © 2006 Wiley Periodicals, Inc. J Graph Theory

We study relational structures (especially graphs and posets) which satisfy the analogue of homogeneity but for homomorphisms rather than isomorphisms. The picture is rather different. Our main results are partial characterizations of countable graphs and posets with this property; an analogue of Fraïssé's theorem; and representations of monoids as endomorphism monoids of such structures.

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d+ 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005

Abstract: We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions.

We present a programme of characterizing Ramsey classes of structures by a combination of the model theory and combinatorics. In particular, we relate the classification programme of countable homogeneous structures (of Lachlan and Cherlin) to the classification of Ramsey classes. As particular instances of this approach we characterize all Ramsey classes of graphs, tournaments and partial ordered sets. We fully characterize all monotone Ramsey classes of relational systems (of any type). We also carefully discuss the role of (admissible) orderings which lead to a new classification of Ramsey properties by means of classes of order-invariant objects.

We show that all graphs with a simple extension property are projective. As a consequence of this result we settle in the affirmative a conjecture of Larose and Tardif and characterize all homogeneous graphs which are projective. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 81–86, 2004

The van der Waerden theorem in Ramsey theory states that, for every $k$ and $t$ and sufficiently large $N$, every $k$-colouring of $[N]$ contains a monochromatic arithmetic progression of length $t$. Motivated by this result, Radoičić conjectured that every equinumerous 3-colouring of $[3n]$ contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are coloured with distinct colours. In this paper, we prove that every 3-colouring of the set of natural numbers for which each colour class has density more than 1/6, contains a 3-term rainbow arithmetic progression. We also prove similar results for colourings of $\mathbb{Z}_n$. Finally, we give a general perspective on other anti-Ramsey-type problems that can be considered.

The van der Waerden theorem in Ramsey theory states that, for every $k$ and $t$ and sufficiently large $N$, every $k$-colouring of $[N]$ contains a monochromatic arithmetic progression of length $t$. Motivated by this result, Radoičić conjectured that every equinumerous 3-colouring of $[3n]$ contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are coloured with distinct colours. In this paper, we prove that every 3-colouring of the set of natural numbers for which each colour class has density more than 1/6, contains a 3-term rainbow arithmetic progression. We also prove similar results for colourings of $\mathbb{Z}_n$. Finally, we give a general perspective on other anti-Ramsey-type problems that can be considered.

Graph homomorphisms are used to study good characterizations for coloring problems Trans. Amer. Math. Soc. 384(1996), 1281–1297; Discrete Math.22(1978), 287–300). Particularly, the following concept arises in this context: A pair of graphs (A, B) is called a homomorphism dualityif for any graph Geither there exists a homomorphism σ : A→ Gor there exists a homomorphism τ : G→ Bbut not both. In this paper we show that maxflow-mincut duality for matroids can be put into this framework using strong maps as homomorphisms. More precisely, we show that, if Ckdenotes the circuit of length k+ 1, the pairs (Ck, Ck+ 1) are the only homomorphism dualities in the class of duals of matroids with the strong integer maxflow-mincut property (Jour. Comb. Theor. Ser.B23(1977), 189–222). Furthermore, we prove that for general matroids there is only a trivial homomorphism duality.

The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic coloring number and oriented chromatic number, have been recently studied. Improving and combining earlier techniques of N. Alon and T. H. Marshall (1998, J. Algebraic Combin.8, 5–13) and A. Raspaud and E. Sopena (1994, Inform. Process. Lett.51, 171–174) we prove here a general result about homomorphisms of colored mixed graphs which implies all these earlier results about planar graphs. We also determine the exact chromatic number of colored mixed trees. For this, we introduce the notion of colored homomorphism for mixed graphs containing both colored arcs and colored edges.

We provide a correspondence between the subjects of duality and density in classes of finite relational structures. The purpose of duality is to characterise the structures Cthat do not admit a homomorphism into a given target Bby the existence of a homomorphism froma structure Ainto C. Density is the order-theoretic property of containing no covers (or “gaps”). We show that the covers in the skeleton of a category of finite relational models correspond naturally to certain instances of duality statements, and we characterise these covers.

If F, Gand Hare graphs, write F→ (G, H) to mean that however the edges of Fare colored red and blue, either the red (partial) subgraph contains a copy of Gor the blue subgraph contains a copy of H. Many interesting questions exist concerning this relation, particularly involving the case in which Fis minimal for this property. A useful tool for constructing graphs relevant to such questions, at least when Gand Hare 3-connected, is developed here, namely graphs called senders. These senders are used to prove a number of theorems about the class of minimal F, as well as various related results. For example, let each of Gand Hbe 3-connected, or a triangle. Then there exists an α> 0 such that if nis sufficiently large, there are at least eαnlognnonisomorphic Fsuch that F→ (G, H) in a minimal way.

It is shown that the class of partial Steiner $ (k,\,l)$-system $ \mathcal{G}$-system $ \mathcal{H}$ $ \mathcal{H}$ $ \mathcal{G}$ and has the edge Ramsey property. This solves a longstanding problem in the area.

Two configurations (i.e., finite planar point sets) are said to be of the same order type, if there is a bijection between them which preserves orientations of triples of points. We show a Ramsey-type result about order types which yields that any configuration of a proper order type (in general position) determinesl+1 distances whose ratios fall into prescribed intervals.

It is proved that for every finite latticeL there exists a finite latticeL' such that for every partition of the points ofL' into two classes there exists a lattice embeddingf:L?L' such that the points off(L) are in one of the classes.

Abstract: Continuing the program, which was started in [4], of determining all minimal asymmetric graphs, it is shown that there are exactly seven finite minimal asymmetric graphs of induced length 4, and that these are at the same time the only finite minimal involution-free graphs of induced length 4. Contrary to the situation for minimal asymmetric/involution-free graphs of induced length >4, the assumption of finiteness is essential.

In this paper we prove that strong postorder path compression systems have linear growth.

We investigate sets of integers for which Rado and Schur theorems are true from the point of view of their local density. We establish the existence of locally sparse Rado and Schur sets in a strong sense.

The aim of this paper is to prove the following extension of the Folkman-Rado-Sanders Finite Union Theorem: For every positive integersr andk there exists a familyL of sets having the following properties:i)ifS1,S2, ...,Sk + 1 are distinct pariwise disjoint elements ofL then there exists nonemptyI ? {1, 2, ...,k + 1} with ?i?ISi?Lii)ifL =L1 ?...?Lr is an arbitrary partition then there existsj = r and pairwise disjoint setsS1,S2, ...,Sk?Lj, such thatLi?ISi?Lj for every nonemptyI ? {1, 2, ...,k}.

We introduce a method by means of which one can simply prove the existence of sparse hypergraphs with large chromatic number. Moreover this method gives the full solution of an Erdös-Ore problem.

The aim of this paper is to present a short combinatorial proof of a theorem of P. Erdős on multiplicative bases of integers. A solution of a problem of P. Erdős and D. J. Newman is also presented.

A diagram is an undirected graph corresponding to the covering relation of a finite poset. We prove that three decision problems related to diagrams are NP-complete.

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n-1+?(n),where ?(n) is bounded away from 0, then there is a constant k0>0 such that, for a.e. Gp, c(Gp)=k0n1+?(n).In other words, to make Gp into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n-1+?(n), where ?(n)?0, thenc(Gp)=o(n1+?(n)), almost surely.

We present a new proof of the Paris-Harrington unprovable (in PA) version of Ramsey's theorem. This also yields a particularly short proof of the Ketonen-Solovay result on rapidly growing Ramsey functions.

We construct posets of dimension 2 with highly chromatic Hasse diagrams. This solves a previous problem by Nesetril and Trotter.

Abstract: IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer.

Abstract: By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK m and does not contain two copies ofK m with more than two vertices in common.

A graph G is called rigid if the identical mapping V(G)→V(G) is the only homomorphism G→;G. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002

A graph Gis called rigidif the identical mapping V(G)→V(G) is the only homomorphism G→G. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002