Zobrazeno 1 - 10
of 676
pro vyhledávání: '"Kwan, Matthew"'
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification is provided by a classical theorem of Babai, Erd\H
Externí odkaz:
http://arxiv.org/abs/2410.06095
One of the foundational theorems of extremal graph theory is Dirac's theorem, which says that if an n-vertex graph G has minimum degree at least n/2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by S\'arkoz
Externí odkaz:
http://arxiv.org/abs/2408.09589
Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state $|\psi\rangle$. Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform $|\psi\
Externí odkaz:
http://arxiv.org/abs/2406.03335
In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erd\H{o}s-R\'enyi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthe
Externí odkaz:
http://arxiv.org/abs/2402.05851
Autor:
Kwan, Matthew, Sauermann, Lisa
Consider a quadratic polynomial $Q(\xi_{1},\dots,\xi_{n})$ of independent Rademacher random variables $\xi_{1},\dots,\xi_{n}$. To what extent can $Q(\xi_{1},\dots,\xi_{n})$ concentrate on a single value? This quadratic version of the classical Little
Externí odkaz:
http://arxiv.org/abs/2312.13826
Autor:
Kwan, Matthew, Wigderson, Yuval
The inertia bound and ratio bound (also known as the Cvetkovi\'c bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number $\alpha(G)$ of a graph $G$ in terms of spectral inform
Externí odkaz:
http://arxiv.org/abs/2312.04925
Autor:
Koval, Illya, Kwan, Matthew
As a discrete analogue of Kac's celebrated question on "hearing the shape of a drum", and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency
Externí odkaz:
http://arxiv.org/abs/2309.09788
An ordered $r$-matching is an $r$-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of $r$-dimensional orders. The theory of ordered 2-matchings is well-developed and has con
Externí odkaz:
http://arxiv.org/abs/2308.12268
There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a
Externí odkaz:
http://arxiv.org/abs/2307.06453
Autor:
Brunck, Florestan, Kwan, Matthew
Recall the classical 15-puzzle, consisting of 15 sliding blocks in a $4\times 4$ grid. Famously, the configuration space of this puzzle consists of two connected components, corresponding to the odd and even permutations of the symmetric group $S_{15
Externí odkaz:
http://arxiv.org/abs/2303.09459