A5056507682- Limits and Structures in Graph Theory
- Advanced Graph Theory Research
- Graph theory and applications
- Advanced Topology and Set Theory
- graph theory and CDMA systems
- Complexity and Algorithms in Graphs
- Graph Labeling and Dimension Problems
- Algorithms and Data Compression
- Computational Geometry and Mesh Generation
- Finite Group Theory Research
- Stochastic processes and statistical mechanics
- COVID-19 Digital Contact Tracing
- Game Theory and Applications
- Opinion Dynamics and Social Influence
- Markov Chains and Monte Carlo Methods
- Complex Network Analysis Techniques
- Privacy, Security, and Data Protection
- Digital Image Processing Techniques
- Artificial Intelligence in Games
- COVID-19 epidemiological studies
- Socioeconomic Development in MENA
- Distributed systems and fault tolerance
- Interconnection Networks and Systems
- Game Theory and Voting Systems
- Advanced Combinatorial Mathematics
Carnegie Mellon University
2015-2024
Microsoft Research (India)
2013
Microsoft (United States)
2013
Princeton University
2006-2010
California Institute of Technology
2003-2006
As COVID-19 hounds the world, common cause of finding a swift solution to manage pandemic has brought together researchers, institutions, governments, and society at large. The Internet Things (IoT), artificial intelligence (AI)-including machine learning (ML) Big Data analytics-as well as Robotics Blockchain, are four decisive areas technological innovation that have been ingenuity harnessed fight this future ones. While these highly interrelated smart connected health technologies cannot...
More than forty years ago, Erdős conjectured that for any $t \leq \frac{n}{k}$ , every k -uniform hypergraph on n vertices without t disjoint edges has at most max ${\binom{kt-1}{k}, \binom{n}{k}-\binom{n-t+1}{k}\}$ edges. Although this appears to be a basic instance of the Turán problem (with -edge matching as excluded hypergraph), progress question remained elusive. In paper, we verify conjecture all < \frac{n}{3k^2}$ . This improves upon best previously known range =...
Abstract We consider several variants of the classical Cops and Robbers game. treat version where robber can move R ≥1 edges at a time, establishing general upper bound , α = 1 + 1/ thus generalizing best known for case due to Lu Peng, Scott Sudakov. also show that in this case, cop number an n ‐vertex graph be as large − 1/( 2) finite ≥5, but linear if is infinite. For 1, we study directed problem, any strongly connected digraph on vertices O ( (loglog ) 2 /log ). Our approach based...
Abstract One of the most famous results in theory random graphs establishes that threshold for Hamiltonicity Erdős‐Rényi graph G n,p is around . Much research has been done to extend this increasingly challenging structures. In particular, a recent result by Frieze determined asymptotic loose Hamilton cycle 3‐uniform hypergraph connecting hypergraphs edge‐colored graphs. work, we consider setting graphs, and prove which achieves best possible first order constant. Specifically, when edges...
Let i t ( G ) be the number of independent sets size in a graph . Engbers and Galvin asked how large could graphs with minimum degree at least δ. They further conjectured that when n ⩾ 2δ 3, is maximized by complete bipartite K δ,n−δ This conjecture has recently drawn attention many researchers. In this short note, we prove conjecture.
In the random $k$-uniform hypergraph $H^{(k)}_{n,p}$ of order $n$, each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a $n$ in which every pair consecutive edges intersects single vertex. It was shown by Frieze that if $p\geq c(\log n)/n^2$ for some absolute constant $c>0$, then a.a.s. $H^{(3)}_{n,p}$ contains cycle, provided divisible $4$. Subsequently, Dudek and extended this result any uniformity $k\ge 4$, proving $p\gg (\log n)/n^{k-1}$,...
Let P_G(q) denote the number of proper q-colorings a graph G. This function, called chromatic polynomial G, was introduced by Birkhoff in 1912, who sought to attack famous four-color problem minimizing P_G(4) over all planar graphs Since then, motivated variety applications, much research done on or maximizing various families graphs. In this paper, we study an old Linial and Wilf, find with n vertices m edges which maximize q-colorings. We provide first approach enables one solve for many...
Abstract Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ⊂ is collection of edges for which there an ordering the vertices v 1 ,…, such that every triple consecutive { i , +1 +2 } edge (indices are considered modulo ). We develop new techniques enable us to prove under certain natural pseudo‐random conditions, almost all can covered by edge‐disjoint cycles, divisible 4. Consequently, we derive corollary random hypergraphs completely packed cycles whp, 4 and p not...
Abstract The classical result in the theory of random graphs, proved by Erdős and Rényi 1960, concerns threshold for appearance giant component graph process. We consider a variant this problem, with Ramsey flavor. Now, each edge that arrives sequence rounds must be colored one r colors. goal can either to create every color class, or alternatively, avoid it color. One analyze offline online setting problem. In paper, we all these variants provide nontrivial upper lower bounds; certain cases...
An old problem raised independently by Jacobson and Schönheim seeks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs edges. In this paper we up constant factor. We show that $m$-edge at least $c (m\log m)^{2/3}$ some absolute $c$, find graphs where estimate is off only multiplicative constant. Our results improve bounds Erdös, Pach, Pyber from 1987.
The classical Kővári–Sós–Turán theorem states that if G is an n -vertex graph with no copy of K s,t as a subgraph, then the number edges in at most O ( 2−1/ s ). We prove one forbids induced and also any fixed H (not necessarily induced) same asymptotic upper bound still holds, different constant factors. This introduces non-trivial angle from which to generalize Turán theory forbidden subgraphs, this paper explores. Along way, we derive on cliques order r -free . result analogue recent Alon...
Abstract Aigner and Fromme initiated the systematic study of cop number a graph by proving elegant sharp result that in every connected planar graph, three cops are sufficient to win natural pursuit game against single robber. This game, introduced Nowakowski Winkler, is commonly known as Cops Robbers combinatorial literature. We extend this directed graphs, establish separation from undirected setting. exhibit geometric construction shows sophisticated robber strategy can indefinitely evade...
In Random Cayley Graphs and Expanders, N. Alon Y. Roichman proved that for every ε > 0 there is a finite c(ε ) such any sufficiently large group G, the expected value of second largest (in absolute value) eigenvalue normalized adjacency matrix graph with respect to log |G| random elements less than . We reduce number )log D(G) (for same c), where sum dimensions irreducible representations G. non-abelian families groups (as measured by these dimensions), asymptotically (1/2)log|G|. As well...
Abstract For a fixed integer r , consider the following random process. At each round, one is presented with edges from edge set of complete graph on n vertices, and asked to choose them. The selected are collected into graph, which thus grows at rate per round. This natural generalization what known in literature as an Achlioptas process (the original version has = 2), been studied by many researchers, mainly context delaying or accelerating appearance giant component. In this article, we...
Abstract Let f be an edge ordering of K n : a bijection . For , we call ( e ) the label An increasing path in is simple (visiting each vertex at most once) such that on greater than previous edge. We let S number edges longest path. Chvátal and Komlós raised question estimating m ): minimum value over all orderings The best known bounds are due respectively to Graham Kleitman, Calderbank, Chung, Sturtevant. Although problem natural, it has seen essentially no progress for three decades. In...
The area of judicious partitioning considers the general family problems in which one seeks to optimize several parameters simultaneously, and these have been widely studied various combinatorial contexts. In this paper, we study essentially most fundamental problem for directed graphs, naturally extends classical Max Cut setting: seek bipartitions many edges cross each direction. It is easy see that a minimum outdegree condition required order be nontrivial, prove every graph with m at...
This article provides a simple proof of the quadratic formula, which also produces an efficient and natural method for solving general equations. The derivation is computationally light conceptually natural, has potential to demystify equations students worldwide.
Let be a graph property which is preserved by removal of edges, and consider the random process that starts with empty n ‐vertex then adds edges one‐by‐one, each chosen uniformly at subject to constraint not violated. These types processes have been extensive research over last 20 years, having striking applications in extremal combinatorics, leading discovery important probabilistic tools. In this paper we k‐matching‐free where containing matching size k . We are able analyze behavior for...
A classical result from graph theory is that every with chromatic number $\chi > t$ contains a subgraph all degrees at least $t$, and therefore copy of $t$-edge tree. Bohman, Frieze, Mubayi recently posed this problem for $r$-uniform hypergraphs. An $r$-tree connected hypergraph no pair edges intersecting in more than one vertex, sequence distinct vertices $(v_1, e_1, \ldots, v_k, e_k)$ $e_i \ni \{v_i, v_{i+1}\}$, where we take $v_{k+1}$ to be $v_1$. proved 2rt$ sufficient embed $t$...
This paper considers two important questions in the well-studied theory of graphs that are F-saturated. A graph G is called F-saturated if does not contain a subgraph isomorphic to F, but addition any edge creates copy F. We first resolve fundamental question minimizing number cliques size r Ks-saturated for all sufficiently large numbers vertices, confirming conjecture Kritschgau, Methuku, Tait, and Timmons. also go further prove corresponding stability result. Next we minimize cycles...