Families of pairs of graphs with a large number of common cards

The vertex‐deleted subgraph G?v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*} common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n≥10. We also present infinite families of pairs of forests and pairs of trees with \begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*} and \begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010     

Path homomorphisms,graph colorings,and boolean matrices

We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path \begin{eqnarray*}\vec{P}\end{eqnarray*} into some orientation \begin{eqnarray*}\vec{G}\end{eqnarray*} of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path \begin{eqnarray*}\vec{P}\end{eqnarray*} depends on the relation between the “algebraic length” and “derived algebraic length” of \begin{eqnarray*}\vec{P}\end{eqnarray*}. 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     

Turánnical hypergraphs

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs G = ([n],E) such that no member of the restriction set \begin{align*}\mathcal {R}\end{align*} = \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced by \begin{align*}\mathcal {R}\end{align*} = {X∈ \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*}: X ∩ [m]≠??}. That is, we determine the maximal number of edges in an n ‐vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r ‐uniform hypergraph \begin{align*}\mathcal R\end{align*} on vertex set [n] is called Turánnical (respectively ε ‐Turánnical), if for any graph G on [n] with more edges than the Turán number t_r(n) (respectively (1 + ε)t_r(n) ), no hyperedge of \begin{align*}\mathcal {R}\end{align*} induces a copy of K_r in G. We determine the thresholds for random r ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐?uczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Judicious partitions of weighted hypergraphs

Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott: Does there exist a bipartition such that each class meets edges of total weight at least (w_1-α)/2+(2w_2)/3? We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes.In particular, it is shown that any graph G with m edges has a partition V_1,..., V_k such that each vertex set meets at least(1-(1-1/k)~2)m + o(m) edges, which answers a related question of Bollobás and Scott.     

An asymptotic version of a conjecture by Enomoto and Ota

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n₁, n₂, …, n_k be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ₂(G)≥n+ k?1, then for any k distinct vertices x₁, x₂, …, x_k in G, there exist vertex disjoint paths P₁, P₂, …, P_k such that |P_i|=n_i and x_i is an endpoint of P_i for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ₁, …, γ_k with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n₀ such that for every graph G of order n≥n₀ with σ₂(G)≥n+ k?1, and for every choice of k vertices x₁, …, x_k∈V(G), there exist vertex disjoint paths P₁, …, P_k in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex x_i is an endpoint of the path P_i, and (γ_i?ε)n<|P_i|<(γ_i + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010     

Crossing numbers of imbalanced graphs

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4n edges is at least constant times e³/n². Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d₁?d₂?···?d_n, then the crossing number satisfies \begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*} with \begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}, and that this bound is tight apart from the values of the constants c₁, c₂>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010     

A Self‐Dual Polar Factorization for Vector Fields

We show that any nondegenerate vector field u in \begin{align*}L^{\infty}(\Omega, \mathbb{R}^N)\end{align*}, where Ω is a bounded domain in \begin{align*}\mathbb{R}^N\end{align*}, can be written as \begin{align*}u(x)= \nabla_1 H(S(x), x)\quad {\text for a.e.\ x \in \Omega}\end{align*}}, where S is a measure‐preserving point transformation on Ω such that \begin{align*}S^2=I\end{align*} a.e. (an involution), and \begin{align*}H: \mathbb{R}^N \times \mathbb{R}^N \to \mathbb{R}\end{align*} is a globally Lipschitz antisymmetric convex‐concave Hamiltonian. Moreover, u is a monotone map if and only if S can be taken to be the identity, which suggests that our result is a self‐dual version of Brenier's polar decomposition for the vector field as \begin{align*}u(x)=\nabla \phi (S(x))\end{align*}, where ? is convex and S is a measure‐preserving transformation. We also describe how our polar decomposition can be reformulated as a (self‐dual) mass transport problem. © 2012 Wiley Periodicals, Inc.     

Pósa's conjecture for graphs of order at least 2 × 108

In 1962 Pósa conjectured that every graph G on n vertices with minimum degree \begin{align*}\delta(G)\ge \frac{2}{3}n\end{align*} contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of Pósa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than \begin{align*}\frac{2}{3}n\end{align*}. Still in 1996, Komlós, Sárközy, and Szemerédi proved Pósa's Conjecture, using the Regularity and Blow‐up Lemmas, for graphs of order n ≥ n₀, where n₀ is a very large constant. Here we show without using these lemmas that n₀:= 2 × 10⁸ is sufficient. We are motivated by the recent work of Levitt, Sárközy and Szemerédi, but our methods are based on techniques that were available in the 90's. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On graphs with a given endomorphism monoid

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M . In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M . Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M , | M |=m there is a graph G with End(G)? M and |E(G)|≤(1 + 0(1))m². This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*} edges. We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009     

On judicious bipartitions of graphs

For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V ₁?V ₂ such that G has at most s edges with both incident vertices in V _i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On randomized greedy matchings

We analyze a randomized greedy matching algorithm (RGA) aimed at producing a matching with a large number of edges in a given weighted graph. RGA was first introduced and studied by Dyer and Frieze in [3] for unweighted graphs. In the weighted version, at each step a new edge is chosen from the remaining graph with probability proportional to its weight, and is added to the matching. The two vertices of the chosen edge are removed, and the step is repeated until there are no edges in the remaining graph. We analyze the expected size μ(G) of the number of edges in the output matching produced by RGA, when RGA is repeatedly applied to the same graph G. Let r(G)=μ(G)/m(G), where m(G) is the maximum number of edges in a matching in G. For a class 𝒢 of graphs, let ρ(𝒢) be the infimum values r(G) over all graphs G in 𝒢 (i.e., ρ is the “worst” performance ratio of RGA restricted to the class 𝒢). Our main results are bound for μ, r, and ρ. For example, the following results improve or generalize similar results obtained in [3] for the unweighted version of RGA; \begin{eqnarray*}r(G)&\ge&{1\over 2-|V|/2|E|}\quad \mbox{(if $G$ has a perfect matching)}\\ {\sqrt{26}-4\over 2}&\le&\rho(\hbox{\sf SIMPLE PLANAR GRAPHS})\le.68436349\\ \rho(\hbox{SIMPLE $\Delta$-GRAPHS})&\ge&{1\over2}+{\sqrt{(\Delta-1)^2+1}-(\Delta-1)\over2}\end{eqnarray*} (where the class is the set of graphs of maximum degree at most Δ). © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 : 353–383, 1997     

Judicious bisection of hypergraphs

Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously.In this paper,we prove that if G is a hypergraph with n vertices and m_i edges of size i for i=1,2,...,k,then G admits a bisection in which each vertex class spans at most(m_1)/2+1/4m_2+…+(1/(2~k)+m_k+o(m_1+…+m_k) edges,where G is dense enough or △(G)= o(n) but has no isolated vertex,which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

Exterior powers of the reflection representation in Springer theory

Let H^*( B_e ) {H^*}\left( {{\mathcal{B}_e}} \right) be the total Springer representation of W for the nilpotent element e in a simple Lie algebra \mathfrakg \mathfrak{g} . Let Λ ⁱ V denote the ith exterior power of the reflection representation V of W. The focus of this paper is on the algebra of W-invariants in

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with \begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*} and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,…,S_k} of {1,…n} which maximizes \begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \begin{align*}\frac{R(B)^2}{C(B)}\end{align*}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some \begin{align*}v_1,\ldots,v_k\in \mathbb{R}^k\end{align*} then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,…,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,…,A_k} of \begin{align*}\mathbb{R}^{k-1}\end{align*} of the quantity \begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle\end{align*}, where for i∈{1,…,k} the vector \begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*} is the Gaussian moment of A_i, i.e., \begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}. We also show that for every ε > 0, achieving an approximation guarantee of \begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*} is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Critical behavior in inhomogeneous random graphs

We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k^‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n^2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n^{(τ‐2)/(τ‐1)}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013     

Dirac's theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \begin{align*}\left\lceil n/2 \right\rceil\end{align*} is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if p ? log n/n, then a.a.s. every subgraph of G(n,p) with minimum degree at least (1/2 + o (1) )np is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability p and the value of the constant 1/2 are asymptotically best possible. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On a bottleneck bipartition conjecture of Erdős

For a graphG, let (U,V)=max{e(U), e(V)} for a bipartition (U, V) ofV(G) withUV=V(G),UV=Ø. Define (G)=min_(U,V ){(U,V)}. Paul Erds conjectures . This paper verifies the conjecture and shows .This work was part of the author's Ph. D. thesis at the University of New Mexico. Research Partially supported by NSA Grant MDA904-92-H-3050.