Search

In this paper we make a partial progress on the following conjecture: for every $\mu>0$ and large enough $n$, every Steiner triple system $S$ on at least $(1+\mu)n$ vertices contains every hypertree $T$ on $n$ vertices. We prove that the conjecture holds if $T$ is a perfect $d$-ary hypertree.

We show that $3$-uniform hypergraphs with the property that all vertices have a quasirandom link graph with density bigger than $1/3$ contain a clique on five vertices. This result is asymptotically best possible.

We show that every 4-uniform hypergraph with $n$ vertices and minimum pair degree at least $(5/9+o(1))n^2/2$ contains a tight Hamiltonian cycle. This degree condition is asymptotically optimal., Dedicated to Endre Szemer\'edi on the occasion of his $80^{\text{th}}$ birthday

Let F be a family of n -element sets. In 1995, Axenovich, Fon-Der-Flaass and Kostochka established an upper bound on the size of F that does not contain a Δ -system with q = 3 sets. Using the ideas of their proof we extend the results to an arbitrary q .

We show that every 3-uniform hypergraph with $n$ vertices and minimum vertex degree at least $(5/9+o(1))\binom{n}2$ contains a tight Hamiltonian cycle. Known lower bound constructions show that this degree condition is asymptotically optimal., 38 pages, second version addresses changes arising from the referee reports

We prove that any Steiner triple system $\mathcal{S}$, with $n = v(\mathcal{S})$ sufficiently large, admits a packing by almost spanning paths that covers almost all edges. More formally, for any $...

In this paper we are interested in the following question: Given an arbitrary Steiner triple system $S$ on $m$ vertices and any 3-uniform hypertree $T$ on $n$ vertices, is it necessary that $S$ contains $T$ as a subgraph provided $m \geq (1+\mu)n$? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive.

A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with $s_1$, $s_2\in S$ and $s_1\leq s_2$ are distinct. Let constants $\alpha>0$ and $0

We investigate the smallest possible minimum degree of $r$-color minimal Ramsey graphs for the $k$-clique. In particular, we obtain a bound of the form $O(k^2\log^2 k\big)$, which is tight up to a $(\log^2 k)$-factor whenever the number $r\geq2$ of colors is fixed. This extends the work of Burr, Erdos, and Lovasz, who determined this extremal value for two colors and any clique size, and complements that of Fox, Grinshpun, Liebenau, Person, and Szabo, who gave essentially tight bounds when the order $k$ of the clique is fixed. As a side product our result also yields an improved upper bound on the vertex Folkman number $F(r,k, k+1)$ of the $k$-clique. The proof relies on a reformulation of the corresponding extremal function by Fox et al. and combines and refines methods used by Dudek, Eaton, and Rodl.

In this paper we study variations of an old result by M\"{u}ller, Reiterman, and the last author stating that a countable graph has a subgraph with infinite degrees if and only if in any labeling of the vertices (or edges) of this graph by positive integers we can always find an infinite increasing path. We study corresponding questions for hypergraphs and directed graphs. For example we show that the condition that a hypergraph contains a subhypergraph with infinite degrees is equivalent to the condition that any vertex labeling contains an infinite increasing loose path. We also find an equivalent condition for a graph to have a property that any vertex labeling with positive integers contains a path of arbitrary finite length, and we study related problems for oriented graphs and labelings with $\mathbb{Z}$ (instead of $\mathbb{N}$). For example, we show that for every simple hypergraph, there is a labelling of its edges by $\mathbb{Z}$ that forbids one-way infinite increasing paths., Comment: 27 pages, 3 figures

A set S ⊂ N of positive integers is a Sidon set if the pairwise sums of its elements are all distinct, or, equivalently, if | ( x + w ) − ( y + z ) | ≥ 1 for every x , y , z , w ∈ S with x y ≤ z w . Let 0 ≤ α 1 be given. A set S ⊂ N is an α-strong Sidon set if | ( x + w ) − ( y + z ) | ≥ w α for every x , y , z , w ∈ S with x y ≤ z w . We prove that the existence of dense strong Sidon sets implies that randomly generated, infinite sets of integers contain dense Sidon sets. We derive the existence of dense strong Sidon sets from Ruzsa's well known result on dense Sidon sets [J. Number Theory 68 (1998), no. 1, 63–71]. We also consider an analogous definition of strong Sidon sets for sets S contained in [ n ] = { 1 , … , n } , and give good bounds for F ( n , α ) = max ⁡ | S | , where S ranges over all α-strong Sidon sets contained in [ n ] .

We show that every $k$-uniform hypergraph on $n$ vertices whose minimum $(k-2)$-degree is at least $(5/9+o(1))n^2/2$ contains a Hamiltonian cycle. A construction due to Han and Zhao shows that this minimum degree condition is optimal. The same result was proved independently by Lang and Sahueza-Matamala., Comment: Dedicated to Endre Szemer\'edi on the occasion of his 80th birthday

In this paper, we study a Ramsey type problems dealing with the number of ordered subgraphs present in an arbitrary ordering of a larger graph. Our first result implies that for every vertex ordered graph G on k vertices and any stochastic vector \(\overrightarrow{a}\) with k! entries, there exists a graph H with the following property: for any linear order of the vertices of H, the number of induced ordered copies of G in H is asymptotically equal to a convex combination of the entries in \(\overrightarrow{a}\). This for a particular choice of \(\overrightarrow{a}\) yeilds an earlier result of Angel, Lyons, and Kechris. We also consider a similar question when the ordering of vertices is replaced by the ordering of pairs of vertices. This problem is more complex problem and we prove some partial results in this case.

By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]=\{1,2,\ldots, n\}$ for some integers $n\ge k\ge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {\L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture., Comment: second version addresses changes arising from the referee reports

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative., Dedicated to the memory of Professor Miroslav Fiedler, 33 pages, second version addresses changes arising from the referee report and includes an appendix with an earlier argument

A set S of integers is a B 3 -set if all the sums of the form a 1 + a 2 + a 3 , with a 1 , a 2 and a 3 ? S and a 1 ? a 2 ? a 3 , are distinct. We obtain asymptotic bounds for the number of B 3 -sets of a given cardinality contained in the interval n = { 1 , ? , n } . We use these results to estimate the maximum size of a B 3 -set contained in a typical (random) subset of n of a given cardinality. These results confirm conjectures recently put forward by the authors On the number of B h -sets, Combin. Probab. Comput. 25 (2016), no. 1, 108-127.

Motivated by a conjecture of Gy\'arf\'as, recently B\"ottcher, Hladk\'y, Piguet, and Taraz showed that every collection $T_1,\dots,T_t$ of trees on $n$ vertices with $\sum_{i=1}^te(T_i)\leq \binom{n}{2}$ and with bounded maximum degree, can be packed into the complete graph on $(1+o(1))n$ vertices. We generalise this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor-closed class of graphs., Comment: 21 pages, accepted for publication in Journal of Combinatorial Theory, Series B

For given integers $k$ and $r$, the Folkman number $f(k;r)$ is the smallest number of vertices in a graph $G$ which contains no clique on $k+1$ vertices, yet for every partition of its edges into $r$ parts, some part contains a clique of order $k$. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for $r=2$ and by Ne\v{s}et\v{r}il and R\"odl (1976) for arbitrary $r$, but these proofs led to very weak upper bounds on $f(k;r)$. Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound on $f(k;2)$. Here, we establish a further improvement by showing an upper bound on $f(k;r)$ which is exponential in a polynomial function of $k$ and $r$. This is comparable to the known lower bound $2^{\Omega(rk)}$. Our proof relies on a recent result of Saxton and Thomason (2015) (or, alternatively, on a recent result of Balogh, Morris, and Samotij (2015)) from which we deduce a quantitative version of Ramsey's theorem in random graphs., Comment: 17 pages, to appear in Combinatorica

Since its formulation, Turan's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a 3-uniform hypergraph F on n vertices in which any five vertices span at least one edge, prove that | F | ≥ ( 1 / 4 − o ( 1 ) ) ( n 3 ) . The construction showing that this bound would be best possible is simply ( X 3 ) ∪ ( Y 3 ) where X and Y evenly partition the vertex set. This construction has the following more general ( 2 p + 1 , p + 1 ) -property: any set of 2 p + 1 vertices spans a complete sub-hypergraph on p + 1 vertices. One of our main results says that, quite surprisingly, for all p > 2 the ( 2 p + 1 , p + 1 ) -property implies the conjectured lower bound.

We investigate extremal problems for hypergraphs satisfying the following density condition. A $3$-uniform hypergraph $H=(V, E)$ is $(d, \eta,P_2)$-dense if for any two subsets of pairs $P$, $Q\subseteq V\times V$ the number of pairs $((x,y),(x,z))\in P\times Q$ with $\{x,y,z\}\in E$ is at least $d|\mathcal{K}_{P_2}(P,Q)|-\eta|V|^3,$ where $\mathcal{K}_{P_2}(P,Q)$ denotes the set of pairs in $P\times Q$ of the form $((x,y),(x,z))$. For a given $3$-uniform hypergraph $F$ we are interested in the infimum $d\geq 0$ such that for sufficiently small $\eta$ every sufficiently large $(d, \eta,P_2)$-dense hypergraph $H$ contains a copy of $F$ and this infimum will be denoted by $\pi_{P_2}(F)$. We present a few results for the case when $F=K_k^{(3)}$ is a complete three uniform hypergraph on $k$ vertices. It will be shown that $\pi_{P_2}(K_{2^r}^{(3)})\leq \frac{r-2}{r-1}$, which is sharp for $r=2,3,4$, where the lower bound for $r=4$ is based on a result of Chung and Graham [Edge-colored complete graphs with precisely colored subgraphs, Combinatorica 3 (3-4), 315-324].

We show that any k-uniform hypergraph with n edges contains two isomorphic edge disjoint subgraphs of size for k = 4, 5 and 6. This is best possible up to a logarithmic factor due to an upper bound construction of Erdős, Pach, and Pyber who show there exist k-uniform hypergraphs with n edges and with no two edge disjoint isomorphic subgraphs with size larger than . Furthermore, our result extends results Erdős, Pach and Pyber who also established the lower bound for k = 2 (eg. for graphs), and of Gould and Rodl who established the result for k = 3. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

A well-known theorem of Erd?s, Ko and Rado implies that any family? ? of k -element subsets of an n -element set with more than? n - t k - t members must contain two members? F and? F ' with | F ? F ' | < t , as long as? n is sufficiently large with respect to? k and? t . We investigate how many such pairs? ( F , F ' ) ? ? × ? there must be in any such family? ? with? | ? | = α n - t k - t and? α 1 .

Motivated by a conjecture of Gyarfas, recently Bottcher, Hladký, Piguet, and Taraz showed that every collection T 1 , … , T n of trees on n vertices with ∑ i = 1 n e ( T i ) ≤ ( n 2 ) and with bounded maximum degree, can be packed into the complete graph on ( 1 + o ( 1 ) ) n vertices. We generalize this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor closed class of graphs.

A setAof positive integers is aBh-setif all the sums of the forma1+ . . . +ah, witha1,. . .,ah∈Aanda1⩽ . . . ⩽ah, are distinct. We provide asymptotic bounds for the number ofBh-sets of a given cardinality contained in the interval [n] = {1,. . .,n}. As a consequence of our results, we address a problem of Cameron and Erdős (1990) in the context ofBh-sets. We also use these results to estimate the maximum size of aBh-sets contained in a typical (random) subset of [n] with a given cardinality.

For fixed r ? 2 , an r -graph ? G = ( V , E ) is an r -uniform hypergraph with vertex set V and edge set E ? ( V r ) . For k ? r ? 2 , let K k denote the complete r -graph on k vertices and let K k ? denote its complement, an independent set on k vertices.The Induced Ramsey Theorem states that for c , r ? 2 and every r -graph G , there exists an r -graph H such that every c -coloring of the edges of H contains a monochromatic induced copy of G . A natural question to ask is what other subgraphs F can be partitioned and have a similar Ramsey property. One can show that if F ? K k or F ? K k ? , then this fails to be true. On the other hand, a result of Abramson and Harrington (1978) and Nesetřil and Rodl (1977) implies that F = K k , as well as F = K k ? , has the Ramsey property.The proof of the Induced Ramsey Theorem was based on a partite lemma and partite construction as shown in Nesetřil and Rodl (1977) and Nesetřil and Rodl (1987). In this note, we present a short proof of this result by eliminating the partite construction to show that the theorem is a direct consequence of the Hales-Jewett Theorem. In other words, we have reduced the proof of this result to one step, rather than two steps.

Let denote the complete k-uniform k-partite hypergraph with classes of size t and the complete k-uniform hypergraph of order s. One can show that the Ramsey number for and satisfies when t = so(1) as s ∞. The main part of this paper gives an analogous result for induced Ramsey numbers: Let be an arbitrary k-partite k-uniform hypergraph with classes of size t and an arbitrary k-graph of order s. We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph such that any red/blue coloring of yields either an induced red copy of or an induced blue copy of ) satisfies . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016

P. Erd\H{o}s [On extremal problems of graphs and generalized graphs, Israel Journal of Mathematics 2 (1964), 183-190] characterised those hypergraphs $F$ that have to appear in any sufficiently large hypergraph $H$ of positive density. We study related questions for $3$-uniform hypergraphs with the additional assumption that $H$ has to be uniformly dense with respect to vertex sets. In particular, we characterise those hypergraphs $F$ that are guaranteed to appear in large uniformly dense hypergraphs $H$ of positive density. We also review the case when the density of the induced subhypergraphs of $H$ may depend on the proportion of the considered vertex sets., Comment: 26 pages, this version addresses changes arising from the referee reports

Extending the concept of Ramsey numbers, Erd?s and Rogers introduced the following function. For given integers 2 ? s < t let f s , t ( n ) = min ? { max ? { | W | : W ? V ( G ) and f s , t ( n ) = G W contains no K s } } , where the minimum is taken over all K t -free graphs G of order n. In this paper, we show that for every s ? 3 there exist constants c 1 = c 1 ( s ) and c 2 = c 2 ( s ) such that f s , s + 1 ( n ) ? c 1 ( log ? n ) c 2 n . This result is best possible up to a polylogarithmic factor. We also show that for all t - 2 ? s ? 4 , there exists a constant c 3 = c 3 ( s ) such that f s , t ( n ) ? c 3 n . In doing so, we partially answer a question of Erd?s by showing that lim n ? ∞ ? f s + 1 , s + 2 ( n ) f s , s + 2 ( n ) = ∞ for any s ? 4 .

In this paper we prove that two local conditions involving the degrees and co-degrees in a graph can be used to determine whether a given vertex partition is Frieze–Kannan regular. With a more refined version of these two local conditions we provide a deterministic algorithm that obtains a Frieze–Kannan regular partition of any graphGin timeO(|V(G)|2).

A set A of non-negative integers is called a Sidon set if all the sums , with and a1, , are distinct. A well-known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of . Results of Chowla, Erdős, Singer and Turan from the 1940s give that . We study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ by a sparse, random subset R of , and ask how large a subset can be, if we require that S should be a Sidon set. Let be a random subset of of cardinality , with all the subsets of equiprobable. We investigate the random variable , where the maximum is taken over all Sidon subsets , and obtain quite precise information on for the whole range of m, as illustrated by the following abridged version of our results. Let be a fixed constant and suppose . We show that there is a constant such that, almost surely, we have . As it turns out, the function is a continuous, piecewise linear function of a that is non-differentiable at two ‘critical’ points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function is constant. Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [n]. Our estimates also directly address a problem raised by Cameron and Erdős (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 1–25, 2015

In this paper we consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer $q$. Given a family $\mathscr{F}$ of $q$-multigraphs, define $ex(n,\mathscr{F})$ to be the maximum number of edges (counting multiplicities) that a $q$-multigraph on $n$ vertices can have without containing a copy of any $F \in \mathscr{F}$ (not necessarily induced). It is well known that $\tau(\mathscr{F}) = \lim_{n \to \infty} ex(n,\mathscr{F})/\binom{n}{2}$ exists for every family $\mathscr{F}$ (finite or infinite). Let $\mathscr{T} = \{\tau(\mathscr{F}) : \mathscr{F} \textrm{ is a family of $q$-multigraphs}\}$. We say the number $\alpha$, $0 \leq \alpha \alpha$, then $\alpha' \geq \alpha + c$. The Erdos--Stone theorem implies that for $q=1$, every $\alpha \in [0,1)$ is a jump. The problem of determining the set of jumps for $q \geq 2$ appears to be much ha...

We prove that finite partial orders with a linear extension form a Ramsey class. Our proof is based on the fact that the class of acyclic graphs has the Ramsey property and uses the partite construction.

For two graphs, $G$ and $F$, and an integer $r\ge2$ we write $G\rightarrow (F)_r$ if every $r$-coloring of the edges of $G$ results in a monochromatic copy of $F$. In 1995, the first two authors established a threshold edge probability for the Ramsey property $G(n,p)\to (F)_r$, where $G(n,p)$ is a random graph obtained by including each edge of the complete graph on $n$ vertices, independently, with probability $p$. The original proof was based on the regularity lemma of Szemer\'edi and this led to tower-type dependencies between the involved parameters. Here, for $r=2$, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers., Comment: 20 pages, second version addresses changes arising from the referee report

For a given r -uniform hypergraph ${\cal F}$ **image** we study the largest blow-up of ${\cal F}$ **image** which can be guaranteed in every large r -uniform hypergraph with many copies of ${\cal F}$ **image** . For graphs this problem was addressed by Nikiforov, who proved that every n -vertex graph that contains Ω(nl) copies of the complete graph Kl must contain a complete l -partite graph with Ω(log n) vertices in each class. We give another proof of Nikiforov's result, make very small progress towards that problem for hypergraphs, and consider a Ramsey-type problem related to a conjecture of Erdős and Hajnal.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 (Part of this work was carried out at the Institute of Advanced Studies in Princeton during the special semester on Arithmetic Combinatorics in Fall 2007 organized by J. Bourgain and V. Vu.)

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f2(n) = n1 + o(1) as n → ∞.

The Frieze-Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The algorithmic applications of this lemma require one to efficiently construct a partition satisfying the conditions of the lemma. R. Williams recently asked if one can construct a partition satisfying the conditions of the Frieze-Kannan regularity lemma in deterministic subcubic time. We resolve this problem by designing an $\tilde O(n^{\omega})$ time algorithm for constructing such a partition, where $\omega < 2.376$ is the exponent of fast matrix multiplication. The algorithm relies on a spectral characterization of vertex partitions satisfying the properties of the Frieze-Kannan regularity lemma.

In 1983, Chvatal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K N with N ⩾ B n vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O ( N 2 − 1 / Δ log 1 / Δ N ) edges, with N = ⌈ B ′ n ⌉ for some constant B ′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is O ( n 2 − 1 / Δ log 1 / Δ n ) . Our approach is based on random graphs; in fact, we show that the classical Erdős–Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n 1/2−ɛ ) ≤ f s,s+k (n) ≤ O(n 1/2+ɛ . In addition, we also discuss some connections between the function f s,t and vertex Folkman numbers.

In 1983 C. Thomassen conjectured that for every k, g∈ℕ there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kuhn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based on a result of Furedi [1983] about hypergraphs. We also show that the analogous conjecture for directed graphs is true. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:316-331,2011 © 2011 Wiley Periodicals, Inc.

The vertex Folkman number F(r,n,m), n0 we derive the linear upper bound when the cliques bigger than (2+ε)n are forbidden.

We consider conditions which allow the embedding of linear hypergraphs of fixed size. In particular, we prove that any k-uniform hypergraph H of positive uniform density contains all linear k-uniform hypergraphs of a given size. More precisely, we show that for all integers ℓ⩾k⩾2 and every d>0 there exists ϱ>0 for which the following holds: if H is a sufficiently large k-uniform hypergraph with the property that the density of H induced on every vertex subset of size ϱn is at least d, then H contains every linear k-uniform hypergraph F with ℓ vertices.The main ingredient in the proof of this result is a counting lemma for linear hypergraphs, which establishes that the straightforward extension of graph ε-regularity to hypergraphs suffices for counting linear hypergraphs. We also consider some related problems.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then $G$ admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph $G$ in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”